首页 > 代码库 > 整理的一些模版LCS(连续和非连续)
整理的一些模版LCS(连续和非连续)
对于连续的最大串，我们称之为子串....非连续的称之为公共序列..
代码：
非连续连续
1 int LCS(char a[],char b[],char sav[]){ 2 int lena=strlen(a); 3 int lenb=strlen(b); 4 int i,j; 5 vector<vector<int> >mat(lena+1); 6 for(int i=0;i<=lena;i++) 7 mat[i].resize(lenb+1,0); 8 for(i=1;i<=lena;i++){ 9 for(j=1;j<=lenb;j++){10 if(a[i-1]==b[j-1])11 mat[i][j]=mat[i-1][j-1]+1;12 else13 mat[i][j]=max(mat[i-1][j],mat[i][j-1]);14 }15 }16 i=lena-1;17 j=lenb-1;18 int k=0;19 while(i!=-1&&j!=-1) {20 if(a[i]==b[j]){21 sav[k++]=a[i];22 i--;23 j--;24 }25 else{26 if(mat[i+1][j+1]==mat[i][j]){27 i--;28 j--;29 }30 else{31 if(mat[i][j+1]>=mat[i+1][j]) i--;32 else j--;33 }34 }35 }36 return k;37 }
连续子串
代码：
1 int LCS(char a[],char b[],char sav[]){ 2 int lena=strlen(a); 3 int lenb=strlen(b); 4 int i,j,k=0,x=0; 5 vector<vector<int> >lcs(lena+1); 6 for(int i=0;i<=lena;i++) 7 lcs[i].resize(lenb+1,0); 8 for(i=1;i<=lena;i++){ 9 for(j=1;j<=lenb;j++)10 if(a[i-1]==b[j-1]){11 lcs[i][j]=lcs[i-1][j-1]+1;12 if(k<lcs[i][j]){13 x=i;14 k=lcs[i][j];15 }16 }17 }18 strncpy(sav,a+(x-k),k);19 return k;20 }
整理的一些模版LCS(连续和非连续)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。