教科书里都是这么讲最长公共子串
方法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）复杂度的，下次学习下。