#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;
}
