最长公共子序列.pptVIP

题目描叙 设计思路： 运行结果 * 最长公共子序列 最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。 最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。 例如，若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的公共子序列。 输入 输入数据有T组测试数据。测试数据的数目 (T)在输入的第一行给出。每组测试数据有两行：每行有一个字符串，每个字符串的长度都不超过20。 输出 每个用例，用一行输出其最大公共子序列的长度，如果没有公共子序列，则输出0。 样例输入 2 abceef 1235896 ABCBDAB BDCABA ? 样例输出 0 4? 动态规划的一个计算最长公共子序列的方法如下： 　　以两个序列 X、Y 为例子： 　　设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有： 　　f[1][1] = same(1,1); 　　f[i,j] = max{f[i-1][j ? 1] + same(i,j),f[i-1,j],f[i,j?1]} 　　其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”，否则为“0”。 　　此时，f中最后一个数便是 X 和 Y 的最长公共子序列的长度　　 该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)。 #includeiostream #includestring using namespace std; int main() { int yongli,hang,lie,i,j; int a[100][100]; cinyongli; 用例个数 getchar(); 吸收回车 while(yongli--) { char x[100],y[100]; gets(x); gets(y); hang=strlen(x); lie=strlen(y); for(i=0;i=hang;i++) a[i][0]=0; 初始化第0列 for(i=0;i=lie;i++) a[0][i]=0; 初始化第0行 for(i=1;i=hang;i++) { for(j=1;j=lie;j++) { if(x[i-1]==y[j-1]) a[i][j]=a[i-1][j-1]+1; 如果对应字符相等，就等于左上角加1 else 否则等于左边和上面中最大的数 { if(a[i-1][j]a[i][j-1]) a[i][j]=a[i-1][j]; else a[i][j]=a[i][j-1]; } } } couta[hang][lie]endl; } return 0; } 代 码 实 现 *