求最长公共子序列实验报告

《求最长公共子序列实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《最长公共子序列》实验报告至学年第学期姓名系别实验地点学号年级、班实验时间年月日实验项目LCS算法一、实验目的了解最长公共子序列问题求解的基本思想掌握实现求最长公共子序列的算法二、实验环境（条件）MicrosoftVisualC++6.0三、程序代码：#include#include#defineN20usingnamespacestd;intLCSlength(char*a,char*b,intc[][N]){intalen=strlen(a);intblen=strlen(b);for(inti

2、=0;i<=alen;i++)c[i][0]=0;for(intj=0;j<=blen;j++)c[0][j]=0;for(i=1;i<=alen;i++)for(j=1;j<=blen;j++)if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;elsec[i][j]=c[i][j-1]>c[i-1][j]?c[i][j-1]:c[i-1][j];returnc[alen][blen];}char*LCS(char*s,char*a,char*b){intc[N][N];inti=strlen(a);in

3、tj=strlen(b);intk=LCSlength(a,b,c);s[k]='';while(k>0){if(c[i][j]==c[i-1][j])i--;elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];i--;j--;}}returns;}voidmain(){char*s=newchar[N];chars1[N];chars2[N];cout<<"Enterthefirstarray:";cin>>s1;cout<<"Enterthesecondarray:";cin>>s

4、2;cout<<"TheLCSis:";cout<