中科大软院算法导论-第五次实验报告-最长公共子序列实验报告.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=bj si，j =2 ai≠bj Li-1,j= Li,j-1 si，j =3 ai≠bj Li-1,j Li,j-1 设Ln,m=k,Sk=c1c2……ck 是序列An和Bm的长度为k的最长公共子序列。最长公共子序列的搜索过程为状态字sn，m开始。搜索过程如下： Sm,n =1 an=bm ck=an 下一个搜索方向是Sn-1,m-1 Sm,n =2 ai≠bj Li-1,j= Li,j-1下一个搜索方向是Sn-1,m Sm,n =3 ai≠bj Li-1,j Li,j-1 下一个搜索方向是Sn,m-1 递推关系： 若si，j =1 则ck=ai，i=i-1，j=j-1，k=k-1 si，j =2 ai≠bj 则i=i-1 si，j =3 ai≠bj 则j=j-1 从i=n，j=m开始搜索，直到i=0或j=0结束，即可得到An和Bm的最长公共子序列。 1.4程序实现及程序截图 1.4.1程序源码 #include stdio.h #include string.h #define MAXLEN 100 void LCSLength(char *x, char *y, char *z,int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i,j,k,len; for(i = 0; i = m; i++) c[i][0] = 0; for(j = 1; j = n; j++) c[0][j] = 0; for(i = 1; i= m; i++) { for(j = 1; j = n; j++) { if(x[i-1] == y[j-1]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = 1; } else if(c[i-1][j] = c[i][j-1]) { c[i][j] = c[i-1][j];