Problem Description A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X =
another sequence Z =
is a subsequence of X if there exists a strictly increasing sequence
of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z =
is a subsequence of X =
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
0
Source
Southeastern Europe 2003
这道题就是求最大公共子序列的长度。
不知道怎么解释。
只好打了个草图。
#include
#include
#define max(a,b) a>b?a:b char s[520]; char s1[520]; int lcs[520][520]; int LCS(int l,int l1) { int i,j; //将两列字符窜变成i行,j列。lsc数组代表每一个位置的最大公共子序列的长度。 for(i=1;i<=l;i++) for(j=1;j<=l1;j++) //将s[i-1]分别和s1的每一个元素做比较 { if(s[i-1]==s1[j-1]) //碰到相等的。 lcs[i][j]=lcs[i-1][j-1]+1;//图中加一的情况 else lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);//碰到不相等的，则取它的上方和左方的那个的最大值，图中都为一。以此累加 } return lcs[l][l1]; //到达最后的状态必然是最大的长度,图中的长度为2，最大公共子序列可以是ca或者ab。 } int main() { while(scanf("%s%s",s,s1)!=EOF) { int l=strlen(s); int l1=strlen(s1); memset(lcs,0,sizeof(lcs)); printf("%d\n",LCS(l,l1)); } return 0; }
|