Kotlin程序员最长公共子串求解方法

【出自WR面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

找出两个字符串的最长公共子串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。

分析与解答：

对于这道题而言，最容易想到的方法就是采用蛮力法，假设字符串s1与s2的长度分别为len1和len2（假设len1≥len2），首先可以找出s2的所有可能的子串，然后判断这些子串是否也是s1的子串，通过这种方法可以非常容易地找出两个字符串的最长子串。当然，这种方法的效率是非常低的，主要原因是：s2中的大部分字符需要与s1进行很多次的比较。那么是否有更好的方法来减少比较的次数呢？下面介绍两种通过减少比较次数从而降低时间复杂度的方法。

方法一：动态规划法

通过把中间的比较结果记录下来，从而可以避免字符的重复比较。主要思路如下：

首先定义二元函数f（i，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））所有的值，从而可以找出最长的子串，如下图所示：(www.xing528.com)

通过上图所示的计算结果，可以求出最长公共子串的长度max与最长子串结尾字符在字符数组中的位置maxI，由这两个值就可以唯一确定一个最长公共子串为“cad”，这个子串在数组中的起始下标为：maxI-max=3，子串长度为max=3。实现代码如下：

程序的运行结果如下：

cad

算法性能分析：

由于这种方法使用了二重循环分别遍历两个字符数组，因此，时间复杂度为O（m*n）（其中，m和n分别为两个字符串的长度），此外，由于这种方法申请了一个m*n的二维数组，因此，算法的空间复杂度也为O（m*n）。很显然，这种方法的主要缺点为申请了m*n个额外的存储空间。

方法二：滑动比较法

如下图所示，这种方法的主要思路是：保持s1的位置不变，然后移动s2，接着比较它们重叠的字符串的公共子串（记录最大的公共子串的长度maxLen，以及最长公共子串在s1中结束的位置maxLenEnd1），在移动的过程中，如果当前重叠子串的长度大于maxLen，则更新maxLen为当前重叠子串的长度。最后通过maxLen和maxLenEnd1就可以找出它们最长的公共子串。实现方法如下图所示：

如上图所示，这两个字符串的最长公共子串为"bc"，实现代码如下：

算法性能分析：

这种方法用双重循环来实现，外层循环的次数为m+n（其中，m和n分别为两个字符串的长度），内层循环最多执行n次，算法的时间复杂度为O（（m+n）*n）。此外，这种方法只使用了几个临时变量，因此算法的空间复杂度为O（1）。