教科书里都是这么讲最长公共子串
方法1. 比较两个串里的每个可能子串，O(n^4)
方法2. 只比较方法1中的其中一个串的前缀形式，O(n^3)
到此为止还是最朴素的方法，然后就：
方法3. 动态规划，O(n^2)
看到这里，我就很奇怪，为什么要用动态规划，难道不能改进方法2吗，同时比较两个串的前缀形式吗，这样就可以O(n^2)了。
下面尝试给出一个算法：
对字符串A的每个字母为起始的前缀子串，单遍扫描字符串B
b_i = B[0]
for each a_i in A:
for a_j,b_j start from current a_i,b_i:
if a_j equals b_j:
update answer
next j
else:
b_i := b_j // skip scanned string in B
next a_i
break
end if
end for
end for
当然仅仅这样是错的，很容易注意到有个问题，比如
A: ababc
B: abababc
最长子串应该是ababc。选定A中首字母a为起始，单遍扫描B，B中的前4个字母与A的前4个字母，已经匹配掉了，不会再返回去。B只剩下最后3个字母，无法再发现最大子串。
但有个解决办法，把A和B换下
A：abababc
B：ababc
就可以了。
所以，给出的算法就是交换AB用上述算法做2次，取大的，时间复杂度还是O(N)
有人可能不信，觉得会有漏洞。
于是我就给出了一个证明：
1476764154873.jpg
1476764236857.jpg
代码如下
int LCS(char astring[], char bstring[]) {
int max_size = 0;
for (int i = 0; i<strlen(astring); i++) {
int current_max_size = 0;
int j = 0, tmp_i = i;
while (j < strlen(bstring) && tmp_i < strlen(astring)) {
if (astring[tmp_i] == bstring[j]) {
current_max_size += 1;
j++;
tmp_i++;
} else {
if (current_max_size == 0) {
++j;
}else {
max_size = current_max_size > max_size ? current_max_size : max_size;
current_max_size = 0;
tmp_i = i;
}
}
}
max_size = current_max_size>max_size ? current_max_size : max_size;
}
return max_size;
}
最后记得正反扫描两次：
int n1 = LCS(astring, bstring);
int n2 = LCS(bstring, astring);
int n = n1 > n2 ? n1 : n2;
这个题是SPOJ1811，但是O（N^2）的算法毫无疑问地超时了。
说明还有改进的空间，据说有个后缀树的算法，是O（N）复杂度的，下次学习下。
