文章目录

1. 1. 最长公共子串&最长公共子序列
   1. 1.1. 最长公共子串
   2. 1.2. 最长公共子序列

最长公共子串&最长公共子序列

---

我们经常需要计算两个字符串的公共部分，也就是子字符串，这时候子字符串的连续性将是我们区分问题的关键点。如果它是连续的，我们要求的是最长公共子串（Longest Common Substring）；如果它不需要连续，我们求得是最长公共子序列（Longest Common Subsequence）。

最长公共子串

---

设lcs[i][j]表示字符串a[0…i]与b[0…j]的最长公共子串的长度。那么最长公共子串的递推公式是

如果a[i]与b[j]相等，那么lcs[i][j]只依赖于lcs[i-1][j-1]的大小，所以lcs[i][j] = lcs[i-1][j-1]+1;

如果a[i]与b[j]不等，那么lcs[i][j]=0；

下面这个是字符串”caba”和”bab”的最长公共子串。

对这个二维数组寻找最大值就能得到最长公共子串了，这点比子序列要复杂点，子序列的最右下角就是它的结果。

最长公共子序列

---

设lcs[i][j]表示字符串a[0…i]与b[0…j]的最长公共子串的长度。那么最长公共子序列的递推公式是

对于第一列和第一行的lcs都为0，因为任意子串和一个空子串相比都是0；

如果a[i]与b[j]相等，那么lcs[i][j] = lcs[i-1][j-1]+1；

如果a[i]与b[j]不等，那么lcs[i][j]就需要依赖a[0…i-1]与b[0…j]的比较结果与a[0…i]与b[0…j-1]的比较结果，所以lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1]);

下面我们就来举个例子，比较字符串”ABCBDAB”和”BDCABA”的最长公共子序列。

这个二维数组的右下角就是它的最长子序列的长度。