最长公共子序列lcs

#include<iostream> #include<cstring> using namespace std; string z,s1,s2; int dp[1010][1010],l1,l2; int main() { cin>>s1>>s2; l1=s1.length(),l2=s2.length(); for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++) if(s1[i-1]==s2[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 i=l1,j=l2; while(i&&j) { if(s1[i-1]==s2[j-1]) { z=s1[--i]+z; j--; } else if(dp[i-1][j]>dp[i][j-1])i--; else j--; } cout<<z; }