Find All Longest Common Subsequence

求所有最大公共子序列的算法实现 - DarkHorse - 博客园
快速的打印出所有的最大长度子序列.

用两个二维数组c[m][n]和b[m][n]，一个用来存储子字符串的LCS长度，一个用来存储路径方向，然后回溯。

其中二维数组b[i][j]的取值为1或2或3，其中取值为1时说明此时xi=yj，c[i][j]=c[i-1][j-1]+1。如果将二维数组看成一个矩阵，那么此时代表了一个从左上角到右下角的路径。如果取值为2，说明xi≠yj,且c[i][j]=c[i-1][j]，代表了一个从上到下的路径，同理取值为3代表一个从左到右的路径。

最后我们可以根据c[m][n]的值知道最大公共子序列的长度。然后根据b[i][j]回溯，可以打印一条LCS。其中b[i][j]=1的坐标点对应的字符同时在两个序列中出现，所以依次回溯这个二维数组就可以找到LCS了。

void GetLCSLen(char *str1, char *str2, Matrix pc, Matrix pb, int nrow, int ncolumn)
14 {
15     int i,j;
16     /************initial the edge***************/
17     for(i=0; i<nrow; i++)
18     {
19         pc[i][0] = 0;
20         pb[i][0] = 0;
21     }
22     for(j=0; j<ncolumn; j++)
23     {
24         pc[0][j] = 0;
25         pb[0][j] = 0;
26     }
27     /************DP*****************************/
28     for(i=1; i<nrow; i++)
29     {
30         for(j=1; j<ncolumn; j++)
31         {
32             if(str1[i-1] == str2[j-1])
33             {
34                 pc[i][j] = pc[i-1][j-1] + 1;//由左上节点转移而来
35                 pb[i][j] = 1;//标记为1
36             }
37             else if(pc[i-1][j] >= pc[i][j-1])
38             {
39                 pc[i][j] = pc[i-1][j];//由上节点转移而来
40                 pb[i][j] = 2;//标记为2
41             }
42             else
43             {
44                 pc[i][j] = pc[i][j-1];//由左节点转移而来
45                 pb[i][j] = 3;//标记为2
46             }
47         }
48     }
49 }
50 void TraceBack(char *str1, Matrix pb, int nrow, int ncolumn)
51 {
52     int ntemp;
53     if(str1 == NULL || pb == NULL)
54         return;
55     if(nrow == 0 || ncolumn == 0)
56         return;
57     ntemp = pb[nrow-1][ncolumn-1];
58     switch(ntemp)
59     {
60     case 1:
61         printf("locate:(%d,%d),%4c\n", nrow-1, ncolumn-1, str1[nrow-2]);//打印公共字符，这里下标是nrow-2，因为矩阵的坐标值(i,j)比字符串的实际下标大1
62         TraceBack(str1, pb, nrow-1, ncolumn-1);//向左上角递归
63         break;
64     case 2:
65         TraceBack(str1, pb, nrow-1, ncolumn);//向上方向递归
66         break;
67     case 3:
68         TraceBack(str1, pb, nrow, ncolumn-1);//向左方向递归
69         break;
70     default:
71         break;
72     }
73 }

http://www.quora.com/How-can-we-efficiently-find-all-the-longest-common-subsequences-of-two-strings
Read full article from 求所有最大公共子序列的算法实现 - DarkHorse - 博客园