公共子序列

GODdad · 2018-07-20 07:50:33 · 个人记录

//我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >，使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。

现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。

include<bits/stdc++.h>

using namespace std;

int p[201][201];

char a[201],b[201];

int m,n,ans;

int main()

{

while(scanf("%s",a+1)==1)
{
scanf("%s",b+1);
n=strlen(a+1);
m=strlen(b+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
    if(a[i]==b[j])
    p[i][j]=p[i-1][j-1]+1;
    else
    p[i][j]=max(p[i-1][j],p[i][j-1]);
}
cout<<p[n][m]<<endl;
}
return 0;

}