中科大軟院算法導(dǎo)論-第五次實(shí)驗(yàn)報(bào)告-最長(zhǎng)公共子序列實(shí)驗(yàn)報(bào)告.doc

第五次實(shí)驗(yàn)報(bào)告最長(zhǎng)公共子序列的生成算法1.1算法應(yīng)用背景最長(zhǎng)公共子序列是一個(gè)序列S ，如果分別是兩個(gè)或多個(gè)已知序列的子序列，且是所有符合此條件序列中最長(zhǎng)的，則S稱(chēng)為已知序列的最長(zhǎng)公共子序列。而最長(zhǎng)公共子串(要求連續(xù))和最長(zhǎng)公共子序列是不同的。最長(zhǎng)公共子序列是一個(gè)十分實(shí)用的問(wèn)題，它可以描述兩段文字之間的“相似度”，即它們的雷同程度，從而能夠用來(lái)辨別抄襲。對(duì)一段文字進(jìn)行修改之后，計(jì)算改動(dòng)前后文字的最長(zhǎng)公共子序列，將除此子序列外的部分提取出來(lái)，這種方法判斷修改的部分，往往十分準(zhǔn)確。簡(jiǎn)而言之，百度知道、百度百科都用得上。1.2算法原理 若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。例： = x, y, z ，A = x y z y x z x z x x x 是長(zhǎng)度為 3 的子序列 x z y z x 是長(zhǎng)度為 5 的子序列例：A = x y z y x z x z，B = x z y x x y z x x x x是長(zhǎng)度為 3 的公共子序列 x z y z 是長(zhǎng)度為 4 的公共子序列 x z y x x z是長(zhǎng)度為 6 的最長(zhǎng)公共子序列1.3算法描述記Ln,m為序列An和Bm的最長(zhǎng)公共子序列長(zhǎng)度，則Li,j為序列Ai和Bj的最長(zhǎng)公共子序列的長(zhǎng)度。根據(jù)最長(zhǎng)公共子序列的性質(zhì)，則得到：階段的劃分和最長(zhǎng)公共子序列長(zhǎng)度的獲取第一階段：計(jì)算A1和Bj的最長(zhǎng)公共子序列的長(zhǎng)度 L1,j ,j=1,2,m第二階段：計(jì)算A2和Bj的最長(zhǎng)公共子序列的長(zhǎng)度 L2,j, j=1,2,m第 n 階段：計(jì)算An和Bj的最長(zhǎng)公共子序列的長(zhǎng)度 Ln,j, j=1,2,m第 n 階段的Lm,n便是序列An和Bm的最長(zhǎng)公共子序列的長(zhǎng)度為了得到An和Bm最長(zhǎng)公共子序列，設(shè)置一個(gè)二維的狀態(tài)字?jǐn)?shù)組si，j，在上述每一個(gè)階段計(jì)算Ln,j 過(guò)程中，根據(jù)公共子序列的性質(zhì)則有按照如下方法把搜索狀態(tài)登記于狀態(tài)字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下一個(gè)搜索方向是Sn-1,mSm,n =3 aibj Li-1,j Li,j-1 下一個(gè)搜索方向是Sn,m-1遞推關(guān)系： 若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開(kāi)始搜索，直到i=0或j=0結(jié)束，即可得到An和Bm的最長(zhǎng)公共子序列。1.4程序?qū)崿F(xiàn)及程序截圖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(最長(zhǎng)公共子序列長(zhǎng)度n); for (i=1;i=m;i+)for (j=1;j=n;j+)printf(%d ,cij);printf(n); printf(最長(zhǎng)公共子序列字符比較n);for (i=1;i=m;i+)for (j=1;j=n;j+)printf(%d ,bij);printf(n);printf(最長(zhǎng)公共子序列為：);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(請(qǐng)按照提示輸入兩個(gè)字符串n);printf(請(qǐng)輸入第一個(gè)字符串：);scanf(%s,x); printf(請(qǐng)輸入第二個(gè)字符串：);scanf(%s,y)