有哪些好方法可以找到两个字符串长度为k的所有常见子序列？
例：
s1 = AAGACC
s2 = AGATAACCAGGAGCTGC
所有常见的长度为5的子序列：AAGAC AAACC AGACC AAGCC
解决方法
一种相对简单的方法是从LCS矩阵重建序列.这是一个O(n ^ 2 * k x * n)算法,其中x是输出的大小(即长度为k的公共子序列的数量).它在C中,但它应该很容易转换为C：
const int N = 100;
int lcs[N][N];
set<tuple<string,int,int>> vis;
string s1 = "AAGACC";
string s2 = "AGATAACCAGGAGCTGC";
void reconstruct(const string& res,int i,int j,int k) {
tuple<string,int> st(res,i,j,k);
if (vis.count(st))
return;
vis.insert(st);
if (lcs[i][j] < k) return;
if (i == 0 && j == 0 && k == 0) {
cout << res << endl;
return;
}
if (i > 0)
reconstruct(res,i-1,k);
if (j > 0)
reconstruct(res,j-1,k);
if (i>0 && j>0 && s1[i-1] == s2[j-1])
reconstruct(string(1,s1[i-1]) + res,k-1);
}
int main() {
lcs[0][0] = 0;
for (int i = 0; i <= s1.size(); ++i)
lcs[i][0] = 0;
for (int j = 0; j <= s1.size(); ++j)
lcs[0][j] = 0;
for (int i = 0; i <= s1.size(); ++i) {
for (int j = 0; j <= s2.size(); ++j) {
if (i > 0)
lcs[i][j] = max(lcs[i][j],lcs[i-1][j]);
if (j > 0)
lcs[i][j] = max(lcs[i][j],lcs[i][j-1]);
if (i > 0 && j > 0 && s1[i-1] == s2[j-1])
lcs[i][j] = max(lcs[i][j],lcs[i-1][j-1] + 1);
}
}
reconstruct("",s1.size(),s2.size(),5);
}
基于稍微不同的DP方法,还应该有O(n *(kx))方法来解决这个问题：设f(i,k)为最小索引j,使得lcs(i,j)> = k .我们已经复发了
f(i,0) = 0 for all i
f(i,k) = min{f(i-1,k),minimum j > f(i-1,k-1) such that s2[j] = s1[i]}
我们还可以从矩阵f重建长度为k的序列.
