最长公共连续子串(LCS)

上一篇博客阐述了最大公共子序列(LCS)的概念，并介绍了最大连续公共子串的概念。与序列不同之处在于前者要求字符必须是连续的而后者则允许字符不连续出现。

下面同样用LCS表示最长公共连续子串。

让我们来分析一下：对于暴力求解法而言，在处理两个字符串A和B时（其中字符串A的长度为x、字符串B的长度为y），那么各个字符串的所有子串数量分别是多少。

n1 = x + (x-1) + ... + 1 = x(x-1) / 2

n2 = y + (y-1) + ... + 1 = y(y-1) / 2

所以，暴力求解法下，对比两个子串是否相等，时间复杂度为O(x^2*y2)，即O(n^4)。

进一步降低计算复杂度的方法是：通过将A集合中的每一个子串与B集合中相应长度范围内的所有子串进行系统性对比分析

如果采用动态规划方法的话，请参照最长公共子序列问题这一经典案例来理解问题本质。在此基础上，请明确dp矩阵的具体意义，并建立相应的状态转移方程以完成求解过程。

子串和子序列的区别在于：连续与否。

假设，两个字符串分别为

A = a1, a2, ..., ax

B = b1, b2, ..., by

我们表示dp[i][j]的意义为：字符串 [a₁,a₂,…,a_i]与字符串[b₁,b₂,…,b_j]之间的最长公共子序列（此处特别指其最后一个字符与这两个字符串