中科大软院算法导论-第五次实验报告-最长公共子序列实验报告.doc

第五次实验报告最长公共子序列的生成算法1.1算法应用背景最长公共子序列是一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。1.2算法原理 若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。例： = x, y, z ，A = x y z y x z x z x x x 是长度为 3 的子序列 x z y z x 是长度为 5 的子序列例：A = x y z y x z x z，B = x z y x x y z x x x x是长度为 3 的公共子序列 x z y z 是长度为 4 的公共子序列 x z y x x z是长度为 6 的最长公共子序列1.3算法描述记Ln,m为序列An和Bm的最长公共子序列长度，则Li,j为序列Ai和Bj的最长公共子序列的长度。根据最长公共子序列的性质，则得到：阶段的划分和最长公共子序列长度的获取第一阶段：计算A1和Bj的最长公共子序列的长度 L1,j ,j=1,2,m第二阶段：计算A2和Bj的最长公共子序列的长度 L2,j, j=1,2,m第 n 阶段：计算An和Bj的最长公共子序列的长度 Ln,j, j=1,2,m第 n 阶段的Lm,n便是序列An和Bm的最长公共子序列的长度为了得到An和Bm最长公共子序列，设置一个二维的状态字数组si，j，在上述每一个阶段计算Ln,j 过程中，根据公共子序列的性质则有按照如下方法把搜索状态登记于状态字si，j中： si，j =1 ai=bjsi，j =2 aibj Li-1,j= Li,j-1si，j =3 aibj Li-1,j= Li,j-1下一个搜索方向是Sn-1,mSm,n =3 aibj Li-1,j Li,j-1 下一个搜索方向是Sn,m-1递推关系： 若si，j =1 则ck=ai，i=i-1，j=j-1，k=k-1si，j =2 aibj 则i=i-1si，j =3 aibj 则j=j-1从i=n，j=m开始搜索，直到i=0或j=0结束，即可得到An和Bm的最长公共子序列。1.4程序实现及程序截图1.4.1程序源码5#include #include #define MAXLEN 100void LCSLength(char *x, char *y, char *z,int m, int n, int cMAXLEN, int bMAXLEN) int i,j,k,len; for(i = 0; i = m; i+) ci0 = 0; for(j = 1; j = n; j+) c0j = 0; for(i = 1; i= m; i+) for(j = 1; j = cij-1) cij = ci-1j; bij = 2; else cij = cij-1; bij = 3; i=m;j=n;k=len=cij;while (i!= 0) &(j != 0) / printf(%d %dn,i,j);switch (bij) case 1: zk=xi-1;k-;j-; case 2:i-;break; case 3:j-;break;printf(最长公共子序列长度n); for (i=1;i=m;i+)for (j=1;j=n;j+)printf(%d ,cij);printf(n); printf(最长公共子序列字符比较n);for (i=1;i=m;i+)for (j=1;j=n;j+)printf(%d ,bij);printf(n);printf(最长公共子序列为：);for (i=1;i=len;i+)printf(%c,zi);printf(n);int main(int argc, char *argv) char xMAXLEN; char yMAXLEN;char zMAXLEN; int bMAXLENMAXLEN; int cMAXLENMAXLEN; int m, n; printf(请按照提示输入两个字符串n);printf(请输入第一个字符串：);scanf(%s,x); printf(请输入第二个字符串：);scanf(%s,y)