#include <stdio.h>
#define MAX 100 char x[MAX+1], y[MAX+1]; int b[MAX+1][MAX+1], c[MAX+1][MAX+1], m, n;
static void init_xy(void); static void lcs_length(void); static void lcs(int i, int j); int main(int argc, char **argv) { init_xy(); lcs_length();
printf("The lowest common subsequence is: "); lcs(m, n); printf("/n");
return 0; }
static void init_xy(void) { int i;
printf("Please input two sequences numbers: "); scanf("%d %d", &m ,&n); getchar();
printf("Please input two sequences:/n"); for(i = 1; i <= m; i++){ scanf("%c", &x[i]); } getchar(); for(i = 1; i <= n; i++){ scanf("%c", &y[i]); } getchar(); }
static void lcs_length(void) { int i, j;
for(i = 1; i <= m; i++){ for(j = 1; j <= n; j++){ if(x[i] == y[j]){ c[i][j] = c[i-1][j-1] + 1; b[i][j] = 1; } else if(c[i-1][j] >= c[i][j-1]){ c[i][j] = c[i-1][j]; b[i][j] = 2; } else{ c[i][j] = c[i][j-1]; b[i][j] = 3; } } } printf("The lowest common subsequence lenght = %d/n", c[m][n]); }
static void lcs(int i, int j) { if(i == 0 || j == 0){ return; }
if(b[i][j] == 1){ lcs(i-1, j-1); printf("%c ", x[i]); } else if(b[i][j] == 2){ lcs(i-1, j); } else{ lcs(i, j-1); } }
执行结果:
[xxxx@localhost suanfa]$ ./a.out Please input two sequences numbers: 7 6 Please input two sequences: ABCBDAB BDCABA The lowest common subsequence lenght = 4 The lowest common subsequence is: B C B A
|