Python实现最长公共子序列-Longest Common Subsequences

定义

一个数列S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则S称为已知序列的最长公共子序列。例如序列X=ABCBDABY=BDCABA。序列BCA是X和Y的一个公共子序列,但是不是X和Y的最长公共子序列,子序列BCBA是X和Y的一个LCS。

复杂度

对于一般性的LCS问题(即任意数量的序列)是属于NP-hard。但当序列的数量确定时,问题可以使用动态规划(Dynamic Programming)在多项式时间解决。

解法

动态规划的一个计算最长公共子序列的方法如下,以两个序列$X=\langle x_1,x_2,…,x_m \rangle$、$Y=\langle y_1,y_2,…,y_n \rangle$为例子,LCS(X,Y)表示X和Y的一个最长公共子序列:
如果$x_m = y_n$,则$LCS(X,Y) = x_m + LCS(x_{m-1},y_{n-1})$
如果$x_m != y_n$,则$LCS(X,Y) = max \lbrace LCS(x_{m-1},Y),LCS(X,y_{n-1}) \rbrace$

为了找到最长的LCS,我们定义dp[i][j]记录LCS的长度,如果X的长度为0或者Y的长度为0,那么LCS=0,即dp[i][j]=0,用i和j分别表示到序列X和序列Y的长度,状态转移方程如下:

$$i=0||j=0,dp[i][j] = 0$$

$$X[i] = Y[j],dp[i][j] = dp[i-1][j-1] + 1$$

$$X[i] != Y[j],dp[i][j] = max \lbrace dp[i-1][j],dp[i][j-1] \rbrace$$

Python实现LCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# -*- coding: utf-8 -*-
"""
Longest Common Subsequences
Created on 2015/7/2 15:11
@author: Wang Xu
"""
class LCS:
def lcs_base(self, input_x, input_y):
if len(input_x) == 0 or len(input_y) == 0:
return ""
else:
a = input_x[0]
b = input_y[0]
if a == b:
return self.lcs_base(input_x[1:], input_y[1:]) + a
else:
# get the max one
return self.getMax(self.lcs_base(input_x[1:], input_y), self.lcs_base(input_x, input_y[1:]))
# construct a list by the input string
def getList(self, inputStr):
listRes = list()
if len(inputStr) != 0:
for i in range(0, len(inputStr)):
listRes.append(inputStr[i])
return listRes
# return the max one between a and b, equivalently return the longest one
def getMax(self, a, b):
if len(a) >= len(b):
return a
else:
return b
if __name__ == '__main__':
lcs = LCS()
l1 = lcs.getList('我的大中国')
l2 = lcs.getList('大中国我的')
l3 = lcs.lcs_base(l1, l2)
print(l3[::-1])
l3 = lcs.lcs_base(l2, l1)
print(l3[::-1])
l1 = '1233433236676'
l2 = '98723765655423'
l3 = lcs.lcs_base(l1, l2)
print(l3[::-1])
l1 = '123s212346我的大中国啊33z'
l2 = '33z的大中国'
l3 = lcs.lcs_base(l1, l2)
print(l3[::-1])

该算法的空间、时间复杂度均为$O(n^{2})$,经过优化后,空间复杂度可为$O(n)$。

LCS变体-最长公共子串

最长公共子串与最长公共子序列稍有区别,不过也算是LCS的一个变体,在LCS中,子序列是不必要求连续的,而子串则是“连续”的。
题:给定两个字符串XY,求二者最长的公共子串,例如X=[aaaba]Y=[ababaa]。二者的最长公共子串为[aba],长度为3。

基本算法

将X的每个子串与Y的每个子串做对比,求出最长公共子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# -*- coding: utf-8 -*-
"""
Created on 2015/7/2 16:13
@author: Wang Xu
"""
# 使用基本算法获取最长公共子串(连续),最长公共子序列可以是非连续的
def getcomlen(firststr, secondstr):
comlen = 0
while firststr and secondstr:
if firststr[0] == secondstr[0]:
comlen += 1
firststr = firststr[1:]
secondstr = secondstr[1:]
else:
break
return comlen
def lcs_base(input_x, input_y):
max_common_len = 0
common_index = 0
for xtemp in range(0, len(input_x)):
for ytemp in range(0, len(input_y)):
com_temp = getcomlen(input_x[xtemp: len(input_x)], input_y[ytemp: len(input_y)])
if com_temp > max_common_len:
max_common_len = com_temp
common_index = xtemp
print('公共子串的长度是:%s' % max_common_len)
print('最长公共子串是:%s' % input_x[common_index:common_index + max_common_len])
if __name__ == '__main__':
lcs_base('d11zabcdeabdcdbbcd', 'bbcd11yabcdefaaa')
'''
OutPut:
公共子串的长度是:5
最长公共子串是:abcde
'''

DP算法

使用动态规划来解最长公共子串问题,可以考虑如何将arr[0,...,i]的问题转化为求解arr[0,...,i-1]的问题,此处考虑使用dp[i][j]表示以X[i]Y[j]结尾的最长公共子串的长度,因为要求子串连续,所以对于X[i]Y[j]来讲,它们要么与之前的公共子串构成新的公共子串;要么就是不构成公共子串;状态转移方程为

$$X[i] = Y[j],dp[i][j] = dp[i-1][j-1] + 1$$

$$X[i] != Y[j],dp[i][j] = 0$$

对于初始化,i=0或者j=0,如果X[i] == Y[j]dp[i][j] = 1;否则dp[i][j] = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class LCS3:
def lcs_dp(self, input_x, input_y):
# input_y as column, input_x as row
dp = [([0] * len(input_y)) for i in range(len(input_x))]
maxlen = maxindex = 0
for i in range(0, len(input_x)):
for j in range(0, len(input_y)):
if input_x[i] == input_y[j]:
if i!=0 and j!=0:
dp[i][j] = dp[i - 1][j - 1] + 1
if i == 0 or j == 0:
dp[i][j] = 1
if dp[i][j] > maxlen:
maxlen = dp[i][j]
maxindex = i + 1 - maxlen
# print('最长公共子串的长度是:%s' % maxlen)
# print('最长公共子串是:%s' % input_x[maxindex:maxindex + maxlen])
return input_x[maxindex:maxindex + maxlen]
if __name__ == '__main__':
lcs3 = LCS3()
print(lcs3.lcs_dp('我是美abc国中defg国中间人', 'abdde我是美中国中国中国人'))
print(lcs3.lcs_dp('cabdec','cbdec'))

参考文献
[1] http://www.ahathinking.com/archives/115.html
[2] http://dsqiu.iteye.com/blog/1701541
[3] http://www.ahathinking.com/archives/122.html

坚持原创技术分享,您的支持将鼓励我继续创作!