Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 33694 Accepted Submission(s): 15330
Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
Source
Southeastern Europe 2003
【轉】百度文庫ppt
引進一個二維數組C，
用C[i,j]記錄Xi與Yj的LCS的長度。
按行、列的序号從小到大地進行遞推計算，
（從第1行開始計算：C[1,1]、C[1,2]、。。。C[1,n]，
再算C[2,1]、C[2,2]、。。。C[2,n]，。。。。。。。。最後計算
C[m,1]、C[m,2]、。。。C[m,n]，最後算出的C[m,n]即
為LCS(X , Y)的長度。）那麼在計算C[i,j]之前，
C[i-1,j-1], C[i-1,j]與C[i,j-1]均已計算出來。此時
根據X[i]=Y[j]還是X[i]¹Y[j]，就可以計算出C[i,j]：
若X[i]=Y[j]，則執行C[i,j]←C[i-1,j-1]+1；
若X[i]¹Y[j]，進行下述判斷：
若C[i-1,j]≥C[i,j-1]則C[i,j]取C[i-1,j]；
否則C[i,j]取C[i,j-1]。
不是很明白代碼2與代碼1的差別--
代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[520],b[520];
int dp[520][520];
int main()
{
while (~scanf("%s",a))
{
scanf("%s",b);
int n=strlen(a);
int m=strlen(b);
memset(dp,0,sizeof(dp));
/* for (int i=0;i<m;i++)
if (a[0]==b[i])
dp[0][i]=1;
for (int i=0;i<n;i++)
if (b[0]==a[i])
dp[i][0]=1;*/
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i-1]==b[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
printf("%d\n",dp[n][m]);
}
return 0;
} WA代碼2：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[520],b[520];
int dp[520][520];
int main()
{
while (~scanf("%s",a))
{
scanf("%s",b);
int n=strlen(a);
int m=strlen(b);
memset(dp,0,sizeof(dp));
for (int i=0;i<m;i++)
if (a[0]==b[i])
dp[0][i]=1;
for (int i=0;i<n;i++)
if (b[0]==a[i])
dp[i][0]=1;
for (int i=1;i<n;i++)
for (int j=1;j<m;j++)
if (a[i]==b[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
printf("%d\n",dp[n-1][m-1]);
}
return 0;
} 最長公共子序列
3000 ms | 記憶體限制：
65535
3
咱們就不拐彎抹角了，如題，需要你做的就是寫一個程式，得出最長公共子序列。
tip：最長公共子序列也稱作最長公共子串(不要求連續)，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分别是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
第一行給出一個整數N(0<N<100)表示待測資料組數
接下來每組資料兩行，分别為待測的兩組字元串。每個字元串長度不大于1000.
輸出
每組測試資料輸出一個整數，表示最長公共子序列長度。每組結果占一行。
樣例輸入
2
asdf
adfsd
123abc
abc123abc
樣例輸出
3
6