【正确答案】对于这道题而言，最容易想到的方法就是采用蛮力法，假设字符串s1与s2的长度分别为len1和len2(假设len1＞=len2)，首先可以找出s2的所有可能的子串，然后判断这些子串是否也是s1的子串，通过这种方法可以非常容易地找出两个字符串的最长子串。当然，这种方法的效率是非常低下的，主要原因为：s2中的大部分字符需要与s1进行很多次的比较。那么是否有更好的方法来减少比较的次数呢?下面介绍两种通过减少比较次数从而降低时间复杂度的方法。
   方法一：动态规划法
   通过把中间的比较结果记录下来，从而可以避免字符的重复比较。主要思路如下：
   首先定义二元函数f(，j)：表示分别以s1[i]，s2[j]结尾的公共子串的长度，显然，f(0，j)=0(j≥0)，f(i，0)=0(i≥0)，那么，对于f(i+1，j+1)而言，则有如下两种取值：
   (1)f(i+1，j+1)=0，当str1[i+1]!=str2[j+1]时；
   (2)f(i+1，j+1)=f(i，j)+1，当str1[i+1]==str2[j+1]时；
   根据这个公式可以计算出f(i，j)(0≤i≤len(s1)，0≤j≤len(s2))所有的值，从而可以找出最长的子串，如下图所示。
   
   通过上图所示的计算结果可以求出最长公共子串的长度max与最长子串结尾字符在字符数组中的位置maxI，由这两个值就可以唯一确定一个最长公共子串为“cad”。这个子串在数组中的起始下标为：maxI-max=3，子串长度为max=3。实现代码如下：
   """
   方法功能: 获取两个字符串的最长公共字串
   输入参数: str1和str2为指向字符的指针
   """
   def getMaxSubStr(str1,str2):
   len1=len(str1)
   len2=len(str2)
   sb="
   maxs=0 #maxs用来记录最长公共字串的长度
   maxI=0 #用来记录最长公共字串最后一个字符的位置
   #申请新的空间来记录公共字串长度信息
   M=[([None]*(len1+1)) for i in range(len2+1)]
   i=0
   while i＜len1+1:
   M[i][0]=0
   i+=1
   j=0
   while j＜len2+1:
   M[0][j]=0
   j+=1
   #通过利用递归公式填写新建的二维数组(公共字串的长度信息)
   i=1
   while i＜len1+1:
   j=1
   while j＜len2+1:
   if list(str1)[i-1]==list(str2)[j-1]:
   M[i][j]=M[i-1][j-1]+1
   if M[i][j]＞maxs:
   maxs=M[i][j]
   maxI=i
   else:
   M[i][j]=0
   j+=1
   i+=1
   #找出公共字串
   i=maxI-maxs
   while i＜maxI:
   sb=sb+list(str1)[i]
   i+=1
   return sb
   
   if __name__=="__main__":
   str1="abccade"
   str2="dgcadde"
   print getMaxSubStr(str1,str2)
   程序的运行结果为：
   cad
   算法性能分析：
   由于这种方法使用了二重循环分别遍历两个字符数组，因此时间复杂度为O(m*n)(其中，m和n分别为两个字符串的长度)。此外，由于这种方法申请了一个m*n的二维数组，因此，算法的空间复杂度也为O(m*n)。很显然，这种方法的主要缺点为申请了m*n个额外的存储空间。
   方法二：滑动比较法
   如下图所示，这种方法的主要思路为：保持s1的位置不变，然后移动s2，接着比较它们重叠的字符串的公共子串(记录最大的公共子串的长度maxLen以及最长公共子串在s1中结束的位置maxLenEnd1)，在移动的过程中，如果当前重叠子串的长度大于maxLen，那么更新maxLen为当前重叠子串的长度。最后通过maxLen和maxLenEnd1就可以找出它们最长的公共子串。实现方法如下图所示：