zixulie.zip_peach

#include<iostream> #include<string> using namespace std; #define N 100 void longest(string s1,string s2) { int max,tep,i,j; int a[N][N]; for(i=0;i<s1.size();i++) for(j=0;j<s2.size();j++) a[i][j]=0; for (j=0;j<s2.size();j++) if (s1[0]==s2[j]) a[0][j]=1; for (i=0;i<s1.size();i++) if (s1[i]==s2[0]) a[i][0]=1; max=a[0][0]; tep=0; for(i=1;i<s1.size();i++) for(j=1;j<s2.size();j++) if(s1[i]==s2[j]) { a[i][j]=a[i-1][j-1]+1; if(max<a[i][j]) { max=a[i][j]; tep=i; } } if(max==0) cout<<"没有公共子序列!"; else{ cout<<"两个字符串的最长公共子序列为:"; for(i=tep-max+1;i<=tep;i++) cout<<s1[i]; cout<<endl; } } /**************************************************************/ // int main() { string s1,s2; cout<<"请输入两个字符串:"<<endl; cout<<"一个字符串为:"; cin>>s1; cout<<"另一个字符串为:"; cin>>s2; longest(s1,s2); cout<<endl; system("PAUSE"); return 0; }