LCS.zip_LCS算法

#include<stdio.h> #include<stdlib.h> #include<string> /*int lcs(char A[],char B[],int n,int m,int L[100][100]) { int j,i; for(i=0;i<=n;i++) L[i][0]=0; for(j=0;j<=m;j++) L[0][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(A[i]==B[j]) L[i][j]=L[i-1][j-1]+1; else L[i][j]=L[i][j-1]>L[i-1][j] ? L[i][j-1]:L[i-1][j]; } } return L[n][m]; } char *max(char A[],int n,int m,int L[100][100],char *x) { int i=n; int k=-1; int j=m; int len=L[n][m]; x=(char *)malloc(sizeof(char)*(len+1)); while(i>0 && j>0) { int max=L[i][j-1]>L[i-1][j] ? L[i][j-1]:L[i-1][j]; if( (L[i][j]==L[i-1][j-1]+1) && L[i][j]!=max ) { k=k+1; x[k]=A[i]; i=i-1; j=j-1; } else if(L[i][j]==L[i][j-1]) j=j-1; else i=i-1; } return x; } int main() { int n,m; int len; printf("输入A串的长度\n"); scanf("%d",&n); char *pa=NULL; pa=(char *)malloc((n+1)*sizeof(char)); if(pa==NULL) exit(-1); printf("输入字符串后并输出结果\n"); for(int i=0;i<n+1;i++) scanf("%c",&pa[i]); for(i=0;i<n+1;i++) printf("%c",pa[i]); printf("\n"); printf("输入b串的长度\n"); scanf("%d",&m); char *pb=NULL; pb=(char *)malloc((m+1)*sizeof(char)); if(pb==NULL) exit(-1); printf("输入字符串后并输出结果\n"); for(i=0;i<=m;i++) scanf("%c",&pb[i]); for(i=0;i<=m;i++) printf("%c",pb[i]); printf("\n"); int L[100][100]; len=lcs(pa,pb,n,m,L); /*for(int j=0;j<=n;j++) { for(int h=0;h<=m;h++) { printf("%d",L[j][h]); } printf("\n"); }*/ /* printf("%d\n",len); char *x=NULL; x=max(pa,n,m,L,x); printf("输出最长公共子序列\n"); for(int k=0;k<len;k++) printf("%c",x[k]); printf("\n"); free(x); return 0; }*/