03_最长公共子序列长度

一、测试输入：

LOOP
HELLOWORLD

二、经转移公式推导：

三、测试程序：

 1 /*
 2  *    最长公共子序列长度
 3  *
 4  */
 5 
 6 #include <stdio.h>
 7 #include <stdlib.h>
 8 #include <string.h>
 9 
10 #define MAX(a, b)    (a)>(b) ? (a):(b)
11 
12 int get_lcs_len(unsigned char *m, unsigned char *n)
13 {
14     int lm = strlen(m);
15     int ln = strlen(n);
16     int max = 0;
17     int i = 1;
18     int j = 1;
19     
20     int (*dp)[ln] = (int (*)[ln])malloc(sizeof(int)*lm*ln);
21     memset(dp, 0, sizeof(int)*lm*ln);
22 
23     for (; i<lm; i++)
24         for (j=1; j<ln; j++) {
25             if (m[i] == n[j])
26                 max = MAX(max, dp[i][j]=dp[i-1][j-1]+1);        
27             else
28                 dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]);
29         }
30 
31     for (i=0; i<lm; i++) {
32         for (j=0; j<ln; j++)
33             printf("%d ", dp[i][j]);
34         puts("");
35     }
36     free(dp);
37 
38     return max;
39 }
40 
41 int main()
42 {
43     unsigned char str1[1024] = {' '};
44     unsigned char str2[1024] = {' '};
45 
46     while (~scanf("%s%s", str1+1, str2+1))
47         printf("%d
", get_lcs_len(str1, str2));
48 
49     return 0;
50 }