7-13 最长公共子序列 (10 分)
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1,x2,…,xm>,则另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k有:
Xij=Zj 例如,序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>,则序列<B,C,A>是X和Y的一个公共子序列,序列 <B,C,B,A>也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列.因为X和Y没有长度大于4的公共子序列。
给定两个序列X=<x1,x2,…,xm>和Y=<y1,y2….yn>.要求找出X和Y的一个最长公共子序列。
输入格式:
共有两行。每行为一个由大写字母构成的长度不超过1000的字符串,表示序列X和Y。
输出格式:
第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列.则输出文件仅有一行输出一个整数0。
输入样例:
ADCBDAB
BDCABC
输出样例:
4
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 M
#include<bits/stdc++.h> using namespace std; #define MAX 1000 char x[MAX],y[MAX]; int c[MAX][MAX],b[MAX][MAX]; void LCS(int i,int j){ if(i==0||j==0) return; if(b[i][j]==1){ LCS(i-1,j-1); cout<<x[i-1]; } else if(b[i][j]==2) LCS(i-1,j); else LCS(i,j-1); } int main(){ cin>>x>>y; int m,n; m=strlen(x); n=strlen(y); int i,j; for(i=1;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(x[i-1]==y[j-1]){ c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j]; b[i][j]=2; } else{ c[i][j]=c[i][j-1]; b[i][j]=3; } } } cout<<c[m][n]; //LCS(m,n); return 0; }