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

《中科大软院算法导论-第五次实验报告-最长公共子序列实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第五次实验报告——最长公共子序列的生成算法1.1算法应用背景最长公共子序列是一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。1.2算法原理若给定序列X={x1,x2,…,xm

2、}，则另一序列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=xyzyxzxzxxx是长度为3的子序列xzyzx是长度为5的子序列例：A=xyzyxzxz，B=xzyxxyzxxxx是长度为3的公共子序列xzyz是长度为4的公共子序列xzyxxz是长度为6的最长公共子序列1.3算法描述记Ln,m为序列An和Bm的最长公共子序

3、列长度，则Li,j为序列Ai和Bj的最长公共子序列的长度。根据最长公共子序列的性质，则得到：5阶段的划分和最长公共子序列长度的获取第一阶段：计算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

4、，j中：si，j=1ai=bjsi，j=2ai≠bjLi-1,j>=Li,j-1si，j=3ai≠bjLi-1,j=Li,j-1下一个搜索方向是Sn-1,mSm,n=3ai≠bjLi-1,j

5、2ai≠bj则i=i-1si，j=3ai≠bj则j=j-1从i=n，j=m开始搜索，直到i=0或j=0结束，即可得到An和Bm的最长公共子序列。1.4程序实现及程序截图1.4.1程序源码5#include#include#defineMAXLEN100voidLCSLength(char*x,char*y,char*z,intm,intn,intc[][MAXLEN],intb[][MAXLEN]){inti,j,k,len;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)5c[0][j

6、]=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;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}i=m;j=n;k=len=c[i][j];while((i!=0)&&(j!=0)){//printf("%d%d",i,j);switch(b[i][j]){case1:z[k]=x[i-1

7、];k--;j--;case2:i--;break;case3:j--;break;}}printf("最长公共子序列长度");for(i=1;i<=m;i++){for(j=1;j<=n;j++){printf("%d",c[i][j]);}printf("");}printf("最长公共子序列字符比较");for(i=1;i<=m;i++){for(j=1;j<=n;j++){printf("%d",b[i][j]);5}printf("");}printf("最长公共子序列为：");for(i=1;i<=len;i++){printf("%c

8、",z[i