// // 最长公共子序列 #include<bits/stdc++.h> using namespace std; const int Size = 1010; //尽量用全局变量 int DP[Size][Size]; int DIR[Size][Size]; int LCS_length(string a, string b) { int M = a.size(); int N = b.size(); for(int i=1; i<=M; i++) { for(int j=1; j<=N; j++) { if(a[i-1] == b[j-1]) { DP[i][j] = DP[i-1][j-1] + 1; DIR[i][j] = 1; } else if(DP[i-1][j] >= DP[i][j-1]) { DP[i][j] = DP[i-1][j]; DIR[i][j] = 2; } else { DP[i][j] = DP[i][j-1]; DIR[i][j] = 3; } } } return DP[M][N]; } void LCS(string a, int i, int j) { if(i==0 || j==0) return; if(DIR[i][j] == 1) { LCS(a, i-1, j-1); cout<<a[i-1]; //a[i-1]==b[j-1] } else if(DIR[i][j]==2) LCS(a, i-1, j); else if(DIR[i][j]==3) LCS(a, i, j-1); } void LCS2(string a, string b, int i, int j) //算法改进,不使用DIR数组,仅仅依靠DP数组以及a,b两个序列 { if(i==0 || j==0) return; if(a[i-1]==b[j-1]) { LCS2(a, b, i-1, j-1); cout<<a[i-1]<<endl; } else if(DP[i-1][j] > DP[i][j-1]) LCS2(a, b, i-1, j); else LCS2(a, b, i, j-1); } int main() { string a, b; cout<<"请输入两个字符串:"<<endl; while(cin>>a>>b && a!="GG") { cout<<"最大公共子序列长度为:"<<LCS_length(a, b)<<endl; // LCS(a, a.size(), b.size()); cout<<"最大公共子序列为:"; LCS2(a, b, a.size(), b.size()); cout<<endl<<"请输入两个字符串:"<<endl; } system("pause"); return 0; } //www.pgcode.top 版权所有