最长公共子序列的长度

最长公共子序列的长度

问题描述：给定两个序列X=<x1, x2,x3,…,xm> 和 Y=<y1, y2, y3,…, yn>, 求X与Y的一个最长公共子序列

问题分析:这个题目的阶段不是明显，没有很明显的上一步、上一层之类的。

既然涉及到公共子序列，也就是有X的第 i 个字符和Y的第 j 个字符相等的情况。

显然如果X[i]=Y[j] 那么长度分别为 i 和 j 的最长公共子序列就是长度分别为 i-1 和 j-1的最长公共子序列加上1.

如果X[i]!=Y[j] 呢？

如果不相等，那么长度为 i 和长度为 j 的序列的最长公共子序列就是“长度为i-1 和 j ” 和“长度为 i 和 j-1 ”中最长公共子序列中较长的一个。

因此可以设计以一个状态f[i, j] 表示起点为 1 ，长度分别为 i 和 j 的最长公共子序列，状态方程可以写为:

(0 <= i <= Len(X) && 0 <= j <= Len(Y))

f[i-1, j-1] + 1 x[i] == y[j]

f[i, j] = f[i-1, j] x[i] != y[j] && Len(f[i-1, j])>=Len(f[i, j-1])

f[i, j-1] x[i] != y[j] && Len(f[i-1, j])<Len(f[i, j-1])

如上图

附代码：

 1 #include<stdio.h>  
 2 #include<string.h>  
 3 #define MAX_LEN 1000  
 4 char sz1[MAX_LEN];  
 5 char sz2[MAX_LEN];  
 6 int aMaxLen[MAX_LEN][MAX_LEN]; /*MaxLen(i, j)表示s1i 和s2j 的最长公共子序列的长度，那么递推关系如下*/  
 7 int main()  
 8 {  
 9     while(scanf("%s%s",sz1+1,sz2+1)>0)  
10     {  
11         int nLength1=strlen(sz1+1);  
12         int nLength2=strlen(sz2+1);  
13         int nTmp;  
14         int i,j;  
15         for(i=0;i<=nLength1;i++)  
16            aMaxLen[i][0]=0;  
17         for(j=0;j<=nLength1;j++)  
18            aMaxLen[0][j]=0;  
19         for(i=1;i<=nLength1;i++)  
20         {  
21             for(j=1;j<=nLength2;j++)  
22             {  
23                 if(sz1[i]==sz2[j])  
24                     aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;  
25                 else  
26                 {  
27                     if(aMaxLen[i][j-1]>aMaxLen[i-1][j])  
28                         aMaxLen[i][j]=aMaxLen[i][j-1];  
29                     else  
30                         aMaxLen[i][j]=aMaxLen[i-1][j];  
31                 }  
32             }  
33         }  
34         printf("%d
",aMaxLen[nLength1][nLength2]);  
35     } 
36 }

View Code

另一种代码，只用一位数组就能搞定，效率挺高，无语了~~~：

 1 #include<iostream>  
 2 #include<cstring>
 3 using namespace std;  
 4 int n,m,maxn,ans,f[1001],i,j;
 5 char a[1001],b[1001];
 6 int main()
 7 {
 8     cin>>a>>b;
 9     n=strlen(a);
10     m=strlen(b);
11     for(int i=0;i<n;i++)  
12     {
13         maxn=0;
14         for(int j=0;j<m;j++)
15         {
16             int l=f[j];
17             if(a[i]==b[j]&&f[j]<maxn+1)f[j]=maxn+1;
18             maxn=max(maxn,l);
19         }
20     }
21     for(int i=0;i<m;i++)if(ans<f[i])ans=f[i];
22     cout<<ans;
23 }

View Code