最长公共子序列C

 1 #include<stdio.h>
 2 #define m 10
 3 #define n 10
 4 int c[m + 1][n + 1];
 5 int b[m+1][n+1];
 6 
 7 void LCS_LENGTH(char *x,char *y)
 8 {
 9     int i,j;
10     for (i = 0; i <= m; i++)
11         c[i][0] = 0;
12     for (j = 0; j <= n; j++)
13         c[0][j] = 0;
14     for (i = 1; i <=m; i++)
15     {
16         for (j = 1; j <= n; j++)
17         {
18             if (x[i] == y[j])
19             {
20                 c[i][j] = c[i - 1][j - 1] + 1;
21                 b[i][j] = -1;
22             }
23             else if (c[i - 1][j] >= c[i][j - 1])
24             {
25                 c[i][j] = c[i - 1][j];
26                 b[i][j] = -2;
27             }
28             else
29             {
30                 c[i][j] = c[i][j - 1];
31                 b[i][j] = -3;
32             }
33         }
34     }
35 }
36 
37 int PRINT_LCS(int b[][n+1], char  *x, int i, int j)
38 {
39     if (i == 0 || j == 0)
40         return 0;
41     if (b[i][j] == -1)
42     {
43         PRINT_LCS(b, x, i - 1, j - 1);
44         printf("%c    ", x[i]);
45     }
46     else if (b[i][j] == -2)
47         PRINT_LCS(b, x, i - 1, j);
48     else
49         PRINT_LCS(b, x, i, j - 1);
50 
51 }
52 
53 
54 int main()
55 {
56 
57     char x[10];
58     char y[10];
59     printf("字符串的值x:");  
60     scanf("%s",x); 
61     printf("字符串的值y:");  
62     scanf("%s",y);
63     LCS_LENGTH(x, y);
64     PRINT_LCS(b, x, 10, 10);
65     return 0;
66 }