首页 > 代码库 > 最长公共子序列的一种解决方法
最长公共子序列的一种解决方法
受http://blog.csdn.net/yysdsyl/article/details/4226630启发，很多内容都是转载它的，或者重新整理加入了一些自己的理解。
C语言
#include <stdio.h>#include <string.h>const int MAXN=100;void print_lcs(int i,int j,char *x,int b[][MAXN]){ if(i==0||j==0) { return; } if(b[i][j]==0) { print_lcs(i-1,j-1,x,b); printf("%c",x[i-1]); } else { if(b[i][j]==1) print_lcs(i-1,j,x,b); else print_lcs(i,j-1,x,b); }}int main(){ char s1[MAXN],s2[MAXN]; int c[MAXN][MAXN],b[MAXN][MAXN]; int n,m; int i,j; scanf("%s",s1); n=strlen(s1); scanf("%s",s2); m=strlen(s2); for(i=0;i<=n+1;i++) c[i][0]=0; for(j=0;j<=m+1;j++) c[0][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(s1[i-1]==s2[j-1]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=0; } else { if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=1; } else { c[i][j]=c[i][j-1]; b[i][j]=-1; } } } } printf("%d\n",c[n][m]); print_lcs(n+1,m+1,s1,b);}Matlab版
function LCS(s1,s2)n=length(s1);m=length(s2);C=zeros(100,100);B=zeros(100,100);for i=1:n for j=1:m if (i==1||j==1) if(s1(i)==s2(j)) C(i,j)=1; else C(i,j)=0; end continue; end if(s1(i)==s2(j)) C(i,j)=C(i-1,j-1)+1; B(i,j)=0; elseif (C(i-1,j)>=C(i,j-1)) C(i,j)=C(i-1,j); B(i,j)=1; else C(i,j)=C(i,j-1); B(i,j)=-1; end endendfprintf(1,‘%g\n‘,C(n,m))print_lcs(n,m,s1,B)fprintf(1,‘\n‘)function print_lcs(i,j,x,B)if(i==0||j==0) returnendif(B(i,j)==0) print_lcs(i-1,j-1,x,B); fprintf(1,‘%s‘,x(i))endif(B(i,j)==1) print_lcs(i-1,j,x,B);endif(B(i,j)==-1) print_lcs(i,j-1,x,B);endend
C++
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <vector>using namespace std ;const int MAXN = 510 ;int dp[MAXN][MAXN] , prex[MAXN][MAXN] , prey[MAXN][MAXN] ;char s1[MAXN] , s2[MAXN] ;int n , m ;int main(){ scanf("%s",s1+1) ; n = strlen(s1+1); scanf("%s",s2+1) ; m = strlen(s2+1) ; memset(dp,-1,sizeof(dp)) ; memset(prex,-1,sizeof(prex)) ; memset(prey,-1,sizeof(prey)) ; dp[0][0] = 0 ; int maxlen = -1 , ansx , ansy ; for (int i = 1 ; i <= n ; i++) for (int j = 1 ; j <= m ; j++){ if (s1[i] != s2[j]) continue ; for (int px = 0 ; px < i ; px++) for (int py = 0 ; py < j ; py++){ if (s1[px] == s2[py] && dp[px][py] + 1 > dp[i][j]){ dp[i][j] = dp[px][py] + 1 ; prex[i][j] = px ; prey[i][j] = py ; } } if (dp[i][j] > maxlen){ maxlen = dp[i][j] ; ansx = i ; ansy = j ; } } printf("Length = %d\n" , dp[ansx][ansy]) ; vector<char> result ; while (ansx != 0 && ansy != 0){ result.push_back(s1[ansx]) ; int tempx = prex[ansx][ansy] ; int tempy = prey[ansx][ansy] ; ansx = tempx ; ansy = tempy ; } for (int i = (int)result.size() - 1 ; i >= 0 ; i--) printf("%c",result[i]); printf("\n"); return 0 ;}内心还是应该有一张C[i][j]二维数组记录LCS的表~
最长公共子序列的一种解决方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。