最长公共子序列/串问题
基础概念
- 字符串：S[0..n]，S是一个字符串，长度为n。S本质上是一个字符数组，数组的每个元素都是一个字符；
- 子序列：设T为S的一个子序列，则如果T[ti]和T[tj]为T的两个字符，ti<tj，那么T[ti]和T[tj]也都是S的字符，且对应的下标si<sj。举个例子，S为adbfhgs，那么abfg就是S的一个子序列，abcfg就不是S的子序列；
- 子串：子串是一种特殊的子序列，它要求tj - ti = sj - si，即子串的字符要在S中连续。还是设S为adbfhgs，那么adbf是S的一个子串，abfg就不是。
- 后缀：S[0..n]，那么S[i..n] (i>=0)都是S的后缀；
- 公共子序列/串：如果R既是S的子序列/串，又是T 的子序列/串，那么R就是S和T 的公共子序列/串。
最长公共子序列
问题描述
有两个字符串S[0...m]和T[0...n]，求S和T的所有最长公共子序列的长度。
例子
设S=adbfhgs，T=hadeubgs，那么S和T的最长公共子序列为R=adbgs，长度为5。
分析
首先考虑暴力求解。枚举S的所有子序列，总共有2m个；然后再枚举T的所有子序列，总共有2n个；最后一一匹配，总的时间复杂度为O(2^(m+n))。显然是不可行的。
考虑一种动态规划的方法。
-
状态表####
dp[i][j]，i和j分别是S和T的下标，dp[i][j]为当前状态下的最长公共子序列的长度。其中i和j分别从0开始递增，即状态表是从左往右，从上往下依次被填满的（假设左上方的i和j都是0）。
-
基础状态####
dp[0][j]=0，dp[i][0]=0。显然当一个字符串为空时，两字符串的最长公共子序列就是空字符串，长度为0
-
状态转移方程####
dp[i][j]=dp[i-1][j-1]+1, S[i]=T[j];
dp[i][j]=max(dp[i-1][j],dp[i][j-1]), S[i]!=T[j].
当S[i]=T[j]时，如果i-1和j-1状态下的最长公共子序列为R，那么i和j状态下的最长公共子序列就为R+S[i] (T[j])，所以长度会加1；
当S[i]!=T[j]，i和j状态下的最长公共子序列要么是i-1和j状态下的最长公共子序列，要么是i和j-1状态下的最长公共子序列，所以长度取这两个最长公共子序列的长度的最大值。
打印
到目前为止，我们已经得到了一张填好的状态表。那么怎么通过这张状态表打印出对应的最长公共子序列呢？
回溯打印最长公共子序列
从状态表的右下方开始，向上回溯。具体算法详见代码。
代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
int slen = s.length();
int tlen = t.length();
vector<vector<int>> dp(slen + 1, vector<int>(tlen + 1, 0));
for (int i = 1; i <= slen; i++)
for (int j = 1; j <= tlen; j++)
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
int lcslen = dp[slen][tlen]; // 最长公共子序列长度
string lcs; // 最长公共子序列
lcs.resize(lcslen);
// 从右下向左上遍历状态表
int i = slen, j = tlen, k = lcslen;
while (i > 0 && j > 0)
{
if (s[i - 1] == t[j - 1])
{
lcs[--k] = s[i - 1];
i--; j--;
}
else if (dp[i - 1][j] < dp[i][j - 1])
j--;
else
i--;
}
cout << "longest common subsequence length: " << lcslen << endl;
cout << "longest common subsequence: " << lcs << endl;
return 0;
}
最长公共子串
问题描述
有两个字符串S[0...m]和T[0...n]，求S和T的所有最长公共子串的长度。
例子
设S=adbfhgs，T=hadeubgs，那么S和T的最长公共子串为R=ad或者gs，长度为2。
分析
首先考虑暴力求解。枚举S的所有子串，总共有(m2+m)/2个；然后再枚举T的所有子序列，总共有(n2+n)/2个；最后一一匹配，总的时间复杂度为O(m2*n2)，也是不可行的。可以使用KMP算法把匹配的复杂度降到O(n)，但是总的复杂度O(m^2*n)还是太高。
考虑一种动态规划的方法。
-
状态表####
dp[i][j]，i和j分别是S和T的下标。注意，这里的dp[i][j]并不是当前状态下的最长公共子串的长度，而是最长公共后缀的长度。举个例子，S为abxcdef，T为frcdef，当i=4，j=3，即i指向d，j指向也是d，则当前字符串abxcd和frcd的最长公共后缀为cd。要明确后缀就是从后往前看，依次进行匹配就行了。其中i和j分别从0开始递增，即状态表是从左往右，从上往下依次被填满的（假设左上方的i和j都是0）。
-
基础状态####
dp[0][j]=0，dp[i][0]=0。显然当一个字符串为空时，两字符串的最长公共子串就是空字符串，长度为0
-
状态转移方程####
dp[i][j]=dp[i-1][j-1]+1, S[i]=T[j];
dp[i][j]=0, S[i]!=T[j];
lcslen=max(lcslen, dp[i][j]).
当S[i]=T[j]时，如果i-1和j-1状态下的最长公共后缀为R，那么i和j状态下的最长公共后缀就为R+S[i] (T[j])，所以长度会加1；设S为abxcdef，T为frcdef，i=4(指向d)，j=3(指向d)，i-1和j-1状态下的最长公共后缀为c，i和j状态下的最长公共后缀就是cd，长度为2；
当S[i]!=T[j]，设S为abxcdef，T为frcdef，i=4(指向d)，j=4(指向e)，则当前字符串abxcd和frcde的最长公共后缀为空，长度为0。
lcslen是最长公共子串的长度，每次更新状态的时候更新。
打印
构建状态表的时候，保存每次检测到的最长公共子串的尾下标，最后从尾下标开始往前查找字符串，直到找到两个不相同的字符为止。
代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
int slen = s.length();
int tlen = t.length();
vector<vector<int>> dp(slen + 1, vector<int>(tlen + 1, 0));
int lcsi, lcsj; // 最长公共子串的尾下标
int lcslen = 0; // 最长公共子串长度
for (int i = 1; i <= slen; i++)
for (int j = 1; j <= tlen; j++)
if (s[i - 1] == t[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > lcslen)
{
lcslen = dp[i][j];
lcsi = i;
lcsj = j;
}
}
string lcs;// 最长公共子串
lcs.resize(lcslen);
for (int i = lcsi - 1, j = lcsj - 1, k = lcslen;
i >= 0 && j >= 0; )
{
if (s[i] == t[j])
{
lcs[--k] = s[i];
i--; j--;
}
else
break;
}
cout << "longest common substring length: " << lcslen << endl;
cout << "longest common substring: " << lcs << endl;
return 0;
}
