lcs.rar_LCS_LCS算法_Lcs.rar_最长公共子序列

/*the longest comman sequence *input :two string s, t, length are n,m respectively 0 if i = 0 or j = 0 *c[i][j] = { c[i-1][j-1] + 1 if s[i] = t[j] max(c[i][j-1],c[i-1][j]) if s[i] != t[j] *output: return c[n][m] */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100 char str1[MAX], str2[MAX]; char B[MAX][MAX]; int l1[MAX],l2[MAX]; int LCS(char *s,char *t) { int i, j, k; int ls = strlen(s+1),lt = strlen(t+1); //printf("%d %d\n",strlen(s),strlen(t)); //printf("%d %d",ls,lt); for(i=0; i<=lt; i++) l1[i] = 0; for(i=1; i<=ls; i++) { for(j=1; j<=lt; j++) { if(s[i] == t[j]) { l2[j] = l1[j-1] + 1; B[i][j] = '1'; } else { if(l2[j-1]>l1[j]) { l2[j] = l2[j-1]; B[i][j] = '2'; } else { l2[j] = l1[j]; B[i][j] = '3'; } } } for(k=0; k<=lt; k++) { l1[k] = l2[k]; } } return l2[lt]; } void Construct(char *s,char b[][MAX], int n, int m) { if(n==0||m==0) { return ; } else { if(b[n][m] == '1') { Construct(s,b,n-1,m-1); printf("%c",s[n]); } else if(b[n][m] =='2') { Construct(s,b,n,m-1); } else { Construct(s,b,n-1,m); } } } int main() { printf("请输入第一个字符串 :\n"); scanf("%s",str1+1); printf("请输入第二个字符串 :\n"); scanf("%s",str2+1); printf("最长公共子序列的长度 :%d\n",LCS(str1, str2)); printf("最长公共子序列 :"); Construct(str1,B,strlen(str1+1),strlen(str2+1)); while(1); return 0; }