找出两个字符串的最长公共子串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。
如何求两个字符串的最长公共子串？
轩辕小不懂 的其他提问
类似问题
运行时异常与一般异常有何异同？
796 阅读
String 和StringBuffer的区别？
796 阅读
怎样将字符串中第一个字母大写？
796 阅读
在Python中如何生成一个随机数？
796 阅读
Python中的不可变集合（frozenset）是什么？
796 阅读
在Python中怎样获取输入？
796 阅读
滑动比较法
这种方法的主要思路为：保持s1的位置不变，然后移动s2，接着比较它们重叠的字符串的公共子串（记录最大的公共子串的长度maxLen以及最长公共子串在s1中结束的位置maxLenEnd1），在移动的过程中，如果当前重叠子串的长度大于maxLen，那么更新maxLen为当前重叠子串的长度。最后通过maxLen和maxLenEnd1就可以找出它们最长的公共子串。实现方法如图9-19所示。
图9-19 滑动窗口方法
在图9-19中，这两个字符串的最长公共子串为“bc”，实现代码如下：
算法性能分析：这种方法用双重循环来实现，外层循环的次数为m+n(其中，m和n分别为两个字符串的长度)，内层循环最多执行n次，算法的时间复杂度为O((m+n)×n)。此外，这种方法只使用了几个临时变量，因此算法的空间复杂度为O(1)。