《算法导论》CLRS算法C++实现（十二）P208 最长公共子序列LCS
给定两个序列X和Y，如果Z既是X的一个子序列又是Y的一个子序列，则称序列Z是X和Y的一个公共子序列。
在最长公共子序列问题（LCS）中，给定了两个序列X=<x 1 ，x 2 ，…，x m >和Y=<y 1 ，y 2 ，…，y n >，希望找出X和Y的最大长度的公共子序列。最直观且容易想到的方法是枚举出X的所有子序列，然后逐一检查看其是否为Y的子序列，并随时记录所发现的最长子序列。这种方法的时间复杂度是指数级的，对于较长的序列来说是不实际的。
LCS问题的最优子结构：
若x m =y n ，则z k =x m =yn且Z k-1 是X m-1 和Y n-1 的最长公共子序列；
若x m ≠y n 且z k ≠x m ，则Z是X m-1 和Y的最长公共子序列；
若x m ≠y n 且z k ≠y n ，则Z是X和Y n-1 的最长公共子序列。
算法： LCS- LENGTH(X, Y)
1 2 m ← length[X] 3 n ← length[Y] 4 for i ← 1 to m 5 do c[i, 0 ] ← 0 6 for j ← 0 to n 7 do c[ 0 , j] ← 0 8 for i ← 1 to m 9 do for j ← 1 to n 10 do if xi = yj 11 then c[i, j] ← c[i - 1 , j - 1 ] + 1 12 b[i, j] ← " ↖ " 13 else if c[i - 1 , j] ≥ c[i, j - 1 ] 14 then c[i, j] ← c[i - 1 , j] 15 b[i, j] ← " ↑ " 16 else c[i, j] ← c[i, j - 1 ] 17 b[i, j] ← ← 18 return c and b
C++实现：
1 #include <iostream>
2 #include <stdio.h>
3 #include < string .h>
4
5 using namespace std;
6
7 enum
8 dir {dInit = 0 , dLeft, dUp, dUpLeft}; // 定义方向初始化值dInit，三个方向左dLeft、上dUp、左上dUpLeft
9
10 void LCSPrint( int **LCS_direction, const char * la, const char * lb, int row, int col)
11 {
12 if (la == NULL || lb == NULL)
13 return ;
14
15 int lengthA = strlen(la);
16 int lengthB = strlen(lb);
17
18 if (lengthA == 0 || lengthB == 0 || !(row < lengthA && col < lengthB))
19 return ;
20
21 if (LCS_direction[row][col] == dUpLeft)
22 {
23 if (row > 0 && col > 0 )
24 LCSPrint(LCS_direction, la, lb, row - 1 , col - 1 );
25
26 printf( " %c " , la[row]);
27 }
28 else if (LCS_direction[row][col] == dUp)
29 {
30 if (row > 0 )
31 LCSPrint(LCS_direction, la, lb, row - 1 , col);
32 }
33 else if (LCS_direction[row][col] == dLeft)
34 {
35 if (col > 0 )
36 LCSPrint(LCS_direction, la, lb, row, col - 1 );
37 }
38 }
39
40 int
41 LCSLength( const char *la, const char * lb)
42 {
43 if (!la || ! lb)
44 return 0 ;
45
46 int lengthA = strlen(la);
47 int lengthB = strlen(lb);
48
49 if (!lengthA || ! lengthB)
50 return 0 ;
51
52 int i, j;
53
54 // 创建并初始化存放长度的二维数组
55 int ** LCS_length;
56 LCS_length = ( int **)( new int [lengthA]);
57 for (i = 0 ; i < lengthA; ++ i)
58 LCS_length[i] = ( int *) new int [lengthB];
59
60 for (i = 0 ; i < lengthA; ++ i)
61 for (j = 0 ; j < lengthB; ++ j)
62 LCS_length[i][j] = 0 ;
63
64 // 创建并初始化存放方向的二维数组，方向在枚举enum dir中定义
65 int ** LCS_direction;
66 LCS_direction = ( int **)( new int [lengthA]);
67 for (i = 0 ; i < lengthA; ++ i)
68 LCS_direction[i] = ( int *) new int [lengthB];
69
70 for (i = 0 ; i < lengthA; ++ i)
71 for (j = 0 ; j < lengthB; ++ j)
72 LCS_direction[i][j] = dInit;
73
74 for (i = 0 ; i < lengthA; ++ i)
75 {
76 for (j = 0 ; j < lengthB; ++ j)
77 {
78 if (i == 0 || j == 0 )
79 {
80 if (la[i] == lb[j])
81 {
82 LCS_length[i][j] = 1 ;
83 LCS_direction[i][j] = dUpLeft;
84 }
85 else
86 {
87 if (i > 0 )
88 {
89 // i > 0不是第一行
90 LCS_length[i][j] = LCS_length[i - 1 ][j];
91 LCS_direction[i][j] = dUp;
92 }
93 if (j > 0 )
94 {
95 // j > 0不是第一列
96 LCS_length[i][j] = LCS_length[i][j - 1 ];
97 LCS_direction[i][j] = dLeft;
98 }
99 }
100 }
101
102 else if (la[i] == lb[j])
103 {
104 LCS_length[i][j] = LCS_length[i - 1 ][j - 1 ] + 1 ;
105 LCS_direction[i][j] = dUpLeft;
106 }
107
108 else if (LCS_length[i - 1 ][j] > LCS_length[i][j - 1 ])
109 {
110 LCS_length[i][j] = LCS_length[i - 1 ][j];
111 LCS_direction[i][j] = dUp;
112 }
113
114 else
115 {
116 LCS_length[i][j] = LCS_length[i][j - 1 ];
117 LCS_direction[i][j] = dLeft;
118 }
119 }
120 }
121 LCSPrint(LCS_direction, la, lb, lengthA - 1 , lengthB - 1 );
122 cout << endl;
123 return LCS_length[lengthA - 1 ][lengthB - 1 ];
124 }
125
126 int main()
127 {
128 const char * la = " ABCBDAB " ;
129 const char * lb = " BDCABA " ;
130 int length = LCSLength(la, lb);
131 cout << " 最长子序列长度为： " << length << endl;
132 return 0 ;
133 }
Python实现：
1 def LCS(la, lb): 2 if la == "" or lb == "" : 3 return 4 lengthA = len(la) 5 lengthB = len(lb) 6 lcs = [[0] for i in range(0, lengthA + 1 )] 7 lcs[0] = [0 for j in range(0, lengthB + 1 )] 8 for i in range(lengthA): 9 for j in range(lengthB): 10 lcs[i + 1].append(lcs[i][j] + 1 if la[i] == lb[j] else max(lcs[i][j + 1], lcs[i + 1 ][j])) 11 i = lengthA - 1 12 j = lengthB - 1 13 lcsstr = "" 14 while True: 15 if i == -1 or j == -1 : 16 break 17 if la[i] == lb[j]: 18 lcsstr = " %s%s " % (la[i], lcsstr) 19 i = i - 1 20 j = j - 1 21 else : 22 if lcs[i][j + 1] > lcs[i + 1 ][j]: 23 i = i - 1 24 else : 25 j = j - 1 26 print lcsstr 27 28 LCS( " ABCBDAB " , " BDCABA " )
标签: Python , 编程 , 算法导论 , C/C++ , 代码实现 , 算法 , CLRS , 最长公共子序列 , LCS
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息查看更多关于《算法导论》CLRS算法C++实现（十二）P208 最长公共子序列LCS的详细内容...
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did48422