©2020-2024 ioDraw All rights reserved,
Privacy Policy
问题描述：给定两个序列，例如 X = “ABCBDAB”、Y = “BDCABA”，求它们的最长公共子序列的长度。
下面是求解时的动态规划表，可以看出 X 和 Y 的最长公共子序列的长度为4：
输出一个最长公共子序列并不难（网上很多相关代码），难点在于输出所有的最长公共子序列，因为 LCS 通常不唯一。
我们需要在动态规划表上进行回溯 —— 从c[m][n]，即右下角的格子，开始进行判断： 如果格子c[i][j]对应的X[i-1] == Y[j-1]
，则把这个字符放入 LCS 中，并跳入c[i-1][j-1]中继续进行判断； 如果格子c[i][j]对应的 X[i-1] ≠ Y[j-1]，则比较c[i-1][
j]和c[i][j-1]的值，跳入值较大的格子继续进行判断； 如果出现c[i-1][j]等于c[i][j-1]
的情况，说明最长公共子序列有多个，故两边都要进行回溯（这里用到递归）。 直到 i 或 j 小于等于零为止，倒序输出 LCS 。
从上图的红色路径显示，X 和 Y 的最长公共子序列有 3 个，分别为 “BDAB”、“BCAB”、“BCBA”。
C++代码：
#include<bits/stdc++.h> using namespace std; string X ; string Y ; vector<
vector<int> > c; // 动态规划表 set<string> lcs; // set保存所有的LCS int lcs_length(int m,
int n) { // 表的大小为(m+1)*(n+1) c = vector<vector<int> >(m+1,vector<int>(n+1)); for
(int i=0; i<m+1; ++i) { for(int j=0; j<n+1; ++j) { // 第一行和第一列置0 if (i == 0 || j
== 0) c[i][j] = 0; else if(X[i-1] == Y[j-1]) c[i][j] = c[i-1][j-1] + 1; else c[i
][j] = max(c[i-1][j], c[i][j-1]); } } return c[m][n]; } void lcs_print(int i,
int j, string lcs_str) { while (i>0 && j>0) { if (X[i-1] == Y[j-1]) { lcs_str.
push_back(X[i-1]); // cout<<X[i-1]<<endl; --i; --j; } else { if (c[i-1][j] > c[i
][j-1]) --i; else if (c[i-1][j] < c[i][j-1]) --j; else { lcs_print(i-1, j,
lcs_str); lcs_print(i, j-1, lcs_str); return; } } } // cout<<lcs_str<<endl;
reverse(lcs_str.begin(),lcs_str.end()); lcs.insert(lcs_str); } int main() { cin
>>X>>Y; int m = X.length(); int n = Y.length(); int length = lcs_length(m, n);
cout<< "The length of LCS is " << length << endl; string str; lcs_print(m, n,
str); set<string>::iterator it = lcs.begin(); for( ; it!=lcs.end(); it++) cout
<< *it << endl; return 0; }
运行效果：