©2020-2024 ioDraw All rights reserved
Problem description ： Given two sequences , for example X = “ABCBDAB”,Y = “BDCABA”, Find the length of their longest common subsequence .
The following is the dynamic programming table when solving , It can be seen that X and Y The length of the longest common subsequence of is 4：
It is not difficult to output a longest common subsequence （ There are many related codes on the Internet ）, The difficulty is to output all the longest common subsequences , because LCS Usually not unique .
We need to do backtracking on the dynamic programming table —— from c[m][n], That is, the lower right corner of the grid , Start judging ： If the grid c[i][j] Corresponding X[i-1] == Y[j-1]
, Put this character in the LCS in , And jump in c[i-1][j-1] Continue to judge in the process ; If the grid c[i][j] Corresponding X[i-1] ≠ Y[j-1], Then compare c[i-1][
j] and c[i][j-1] Value of , Jump into the larger value of the grid to continue to judge ; If it appears c[i-1][j] be equal to c[i][j-1]
The situation of , Indicates that there are more than one longest common subsequence , So both sides have to go back （ Recursion is used here ）. until i or j Less than or equal to zero , Reverse order output LCS .
From the red path shown above ,X and Y The longest common subsequence of is 3 individual , They are “BDAB”,“BCAB”,“BCBA”.
C++ code ：
#include<bits/stdc++.h> using namespace std; string X ; string Y ; vector<
vector<int> > c; // Dynamic planning table set<string> lcs; // set Save all LCS int lcs_length(int m,
int n) { // The size of the table is (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) { // First row and first column 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; }
Operation effect ：
Technology