問題描述
我們稱序列 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 的子序列。
輸入數據
輸入包括多組測試數據。每組數據包括一行，給出兩個長度不超過200 的字符串，表示
兩個序列。兩個字符串之間由若干個空格隔開。
輸出要求
對每組輸入數據，輸出一行，給出兩個序列的最大公共子序列的長度。
輸入樣例
abcfbc abfcab
programming contest
abcd mnp
輸出樣例
4
2
0
解題思路
如果我們用字符數組 s1、s2 存放兩個字符串，用s1[i]表示s1 中的第i 個字符，s2[j]表
示s2 中的第j 個字符（字符編號從1 開始，不存在“第0 個字符”），用s1i 表示s1 的前i
個字符所構成的子串， s2j 表示s2 的前j 個字符構成的子串，MaxLen(i, j)表示s1i 和s2j 的
最長公共子序列的長度，那麼遞推關系如下：
[cpp]
if( i ==0 || j == 0 )
{
MaxLen(i, j) = 0 //兩個空串的最長公共子序列長度當然是0}
else
if( s1[i] == s2[j] )
MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1; else { MaxLen(i, j) = Max( MaxLen(i, j-1), MaxLen(i-1, j)); }MaxLen(i, j) = Max( MaxLen(i, j-1), MaxLen(i-1, j)) 這個遞推關系需要證明一下。我們用反證法來證明，MaxLen(i, j)不可能比MaxLen(i, j-1)和MaxLen(i-1, j)都大。先假設MaxLen(i,j)比MaxLen(i-1, j)大。如果是這樣的話，那麼一定是s1[i]起作用了，即s1[i]是s1i 和s2j 的最長公共子序列裡的最後一個字符。同樣，如果MaxLen(i, j)比MaxLen(i, j-1)大，也能夠推導出，s2[j]是s1i 和s2j 的最長公共子序列裡的最後一個字符。即，如果MaxLen(i, j)比MaxLen(i, j-1)和MaxLen(i-1, j)都大，那麼，s1[i]應該和s2[j]相等。但這是和應用本遞推關系的前提----- s1[i]≠s2[j]相矛盾的。因此，MaxLen(i, j)不可能比MaxLen(i, j-1)和MaxLen(i-1, j)都大。MaxLen(i, j)當然不會比MaxLen(i, j-1)和MaxLen(i-1, j)中的任何一個小，因此，MaxLen(i, j) = Max( MaxLen(i, j-1), MaxLen(i-1, j)) 必然成立。顯然本題目的“狀態”就是s1 中的位置i 和s2 中的位置j。“值”就是MaxLen(i, j)。狀態的數目是s1 長度和s2 長度的乘積。可以用一個二維數組來存儲各個狀態下的“值”。本問題的兩個子問題，和原問題形式完全一致的，只不過規模小了一點。參考程序：
[cpp]
#include<stdio.h>
#include<string.h>
#define MAX_LEN 1000
char sz1[MAX_LEN];
char sz2[MAX_LEN];
int aMaxLen[MAX_LEN][MAX_LEN]; /*MaxLen(i, j)表示s1i 和s2j 的最長公共子序列的長度，那麼遞推關系如下*/
int main()
{
while(scanf("%s%s",sz1+1,sz2+1)>0)
{
int nLength1=strlen(sz1+1);
int nLength2=strlen(sz2+1);
int nTmp;
int i,j;
for(i=0;i<=nLength1;i++)
aMaxLen[i][0]=0;
for(j=0;j<=nLength1;j++)
aMaxLen[0][j]=0;
for(i=1;i<=nLength1;i++)
{
for(j=1;j<=nLength2;j++)
{
if(sz1[i]==sz2[j])
aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;
else
{
if(aMaxLen[i][j-1]>aMaxLen[i-1][j])
aMaxLen[i][j]=aMaxLen[i][j-1];
else
aMaxLen[i][j]=aMaxLen[i-1][j];
}
}
}
printf("%d\n",aMaxLen[nLength1][nLength2]);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define MAX_LEN 1000
char sz1[MAX_LEN];
char sz2[MAX_LEN];
int aMaxLen[MAX_LEN][MAX_LEN]; /*MaxLen(i, j)表示s1i 和s2j 的最長公共子序列的長度，那麼遞推關系如下*/
int main()
{
while(scanf("%s%s",sz1+1,sz2+1)>0)
{
int nLength1=strlen(sz1+1);
int nLength2=strlen(sz2+1);
int nTmp;
int i,j;
for(i=0;i<=nLength1;i++)
aMaxLen[i][0]=0;
for(j=0;j<=nLength1;j++)
aMaxLen[0][j]=0;
for(i=1;i<=nLength1;i++)
{
for(j=1;j<=nLength2;j++)
{
if(sz1[i]==sz2[j])
aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;
else
{
if(aMaxLen[i][j-1]>aMaxLen[i-1][j])
aMaxLen[i][j]=aMaxLen[i][j-1];
else
aMaxLen[i][j]=aMaxLen[i-1][j];
}
}
}
printf("%d\n",aMaxLen[nLength1][nLength2]);
}
return 0;
}
