动态规划3.2 最长公共子串

问题：

　　最长公共子串是编辑距离的一种，只允许增加、删除字符两种编辑操作，它表征的也是两个字符串之间的相似程度。

代码：

 1 #include <iostream>
 2 #include <string.h>
 3 
 4 int max3(int a, int b, int c)
 5 {
 6     int tmp = a > b ? a : b;
 7     if(tmp > c)
 8         return tmp;
 9     return c;
10 }
11 
12 int main()
13 {
14     const char *a = "mitcmu";
15     const char *b = "mtacnu";
16     
17     int lena = strlen(a);
18     int lenb = strlen(b);
19     
20     int **states = new int*[lena];
21     for(int i = 0; i < lena; i++)
22     {
23         states[i] = new int[lenb];
24         memset(states[i], 0, sizeof(int) * lenb);
25     }
26     
27     //  初始化第0行
28     for(int i = 0; i < lenb; i++)
29     {
30         if(a[0] == b[i])
31         {
32             states[0][i] = 1;
33         }
34         else if(i == 0)
35         {
36             states[0][i] = 0;
37         }
38         else
39         {
40             states[0][i] = states[0][i - 1];
41         }
42     }
43     
44     // 初始化第0列
45     for(int j = 0; j < lena; j++)
46     {
47         if(a[j] == b[0])
48         {
49             states[j][0] = 1;
50         }
51         else if(j == 0)
52         {
53             states[j][0] = 0;
54         }
55         else
56         {
57             states[j][0] = states[j - 1][0];
58         }
59     }
60         
61     for(int i = 1; i < lena; i++)
62     {
63         for(int j = 1; j < lenb; j++)
64         {
65             if(a[i] == b[j])
66             {
67                 states[i][j] = max3(states[i-1][j], states[i][j-1], states[i-1][j-1] + 1);
68             }
69             else
70             {
71                 states[i][j] = max3(states[i-1][j], states[i][j-1], states[i-1][j-1]);
72             }
73         }
74     }
75     
76     for(int i = 0; i < lena; i++)
77         delete states[i];
78     
79     delete states;
80     
81     std::cout << "max_lcs : " << states[lena - 1][lenb - 1] << std::endl;
82     
83     return 0;
84 }

运行结果：