最长公共子序列

题目：给定两个字符串，求这两个字符串的最长公共子序列。

例如：cnblog 和 belogn 的最长公共子序列是blog。

0 , i == 0 || j == 0

思路：利用动态规划的思想 C[i][j] = max{C[i-1][j], C[i][j-1]}, x[i] != y[j]

C[i-1][j-1] + 1 , x[i] == y[j]

代码如下：

 1 void LongestCommenSubSequence(char Str1[], int M, char Str2[], int N)
 2 {
 3     assert (Str1 != NULL);
 4 
 5     assert (M > 0);
 6 
 7     assert (Str2 != NULL);
 8 
 9     assert (N > 0);
10 
11     int *C = NULL;
12 
13     if (NULL == (C = (int *)malloc ((M + 1) * (N + 1) * sizeof (int))))
14     {
15         printf ("Fail to malloc space to C.\n");
16         exit (1);
17     }
18 
19     for (int i = 0; i <= M; ++i)
20     {
21         for (int j = 0; j <= N; ++j)
22         {
23             if ((0 == i) || (0 == j))
24             {
25                 // 初始化第0行和第列
26                 C[i * (N + 1) + j] = 0;
27                 continue;
28             }
29 
30             if (Str1[i - 1] == Str2[j - 1])
31             {
32                 // C[i][j] = C[i - 1][j-1] + 1
33                 C[i * (N + 1) + j] = C[(i - 1) * (N + 1) + (j - 1)] + 1;
34             }
35             else
36             {
37                 // C[i][j] = max{C[i-1][j], C[i][j-1]}
38                 C[i * (N + 1) + j] = C[(i - 1) * (N + 1) + j] > C[i * (N + 1) + (j - 1)] ? C[(i - 1) * (N + 1) + j] : C[i * (N + 1) + (j - 1)];
39             }
40         }
41     }
42 
43     // 定义一个栈用来保存最长序列，因为是回溯法找，最先找到的字符要最后输出
44     char Stack[MAX];
45     int nTop = -1;
46     int i = M;
47     int j = N;
48 
49     bool bFlag = true;
50 
51     while (bFlag)
52     {
53         if ((C[i * (N + 1) + j] > C[(i - 1) * (N + 1) + (j - 1)]) && (C[i * (N + 1) + j] > C[(i - 1) * (N + 1) + j]))
54         {
55             // 说明Str1[i] == Str2[j]，入栈
56             Stack[++nTop] = Str1[i - 1];
57         }
58 
59         if ((0 == C[(i - 1) * (N + 1) + (j - 1)]) && (0 == C[(i - 1) * (N + 1) + j]))
60         {
61             // 上面和左上角元素都为0，说明没有必要再回溯
62             bFlag = false;
63             continue;
64         }
65 
66         // 寻找回溯的方向
67         if (C[(i - 1) * (N + 1) + j] > C[(i - 1) * (N + 1) + (j - 1)])
68         {
69             // 上面大，就往上面走
70             --i;
71         }
72         else
73         {
74             // 否则都往左上角方向走
75             --i;
76             --j;
77         }
78     }
79 
80     if (-1 == nTop)
81     {
82         printf ("这两个字符串没有公共子序列.\n");
83         return;
84     }
85 
86     printf ("这两个字符串的最长公共子序列为:\n");
87 
88     while (nTop >= 0)
89     {
90         printf ("%c", Stack[nTop--]);
91     }
92 
93     printf ("\n");
94 }

测试结果：