最长公共子序列(lcs)算法实验

《最长公共子序列(lcs)算法实验》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、试验四.最长公共子序列(LCS)算法一．实验原理对于给定的两个序列A和B，如果序列C既是A的子序列，又是B的子序列，则称C是A和B的公共子序列，A和B的公共子序列可能不止一个，其中最长的那个序列称为公共子序列。公共子序列在很多实际应用中起关键作用。序列A={abdledefiess},B={abwdifgdefiesa}，最长公共子序列为C={defies}二．实验目的本次实验就是要找出两个序列XY的最长公共子序列LCS三．实验步骤1.查找公共子序列2.输出公共子序列核心算法代码如下：int**lcs_lengt

2、h(charp[],charq[],int**c,int**k,intm,intn){inti,j;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(p[i-1]==q[j-1])//如果两个字母相等的情况{c[i][j]=c[i-1][j-1]+1;k[i][j]=1;}else{if(c[i-1][j]>=c[i][j-1])//两字母不等情况1{c[i][j]=c[i-1][j];k[i][j]=2;}else//两字母不等情况2{c[i][j]=c[i][j-1];k[i][j

3、]=3;}}}}returnc,k;}输出代码voidprint_lcs(int**k,charp[],inti,intj){if(i==0

4、

5、j==0)return;if(k[i][j]==1){print_lcs(k,p,i-1,j-1);//通过递归的方法按照输入的从头到尾的顺序输出LCScout<

6、两个序列的最长公共子序列,达到了本次实验的目的.