1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int N=1005; 5 6 string x,y; 7 int a[N][N]; 8 int main(){ 9 cin>>x>>y; 10 int lenx=x.length(),leny=y.length(); 11 for(int i=1;i<=leny;i++){ 12 for(int j=1;j<=lenx;j++){ 13 a[i][j]=max(a[i-1][j],a[i][j-1]); 14 if(y[i-1]==x[j-1]) 15 a[i][j]=max(a[i][j],a[i-1][j-1]+1); 16 } 17 } 18 cout<<a[leny][lenx]; 19 return 0; 20 }
最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,LCS)的区别为:子串是串的一个连续的部分,子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;也就是说,子串中字符的位置必须是连续的,子序列则可以不必连续。