用python实现最长公共子序列算法(找到所有最长公共子串)

软件安全的一个小实验，正好复习一下LCS的写法。

实现LCS的算法和算法导论上的方式基本一致，都是先建好两个表，一个存储在(i,j)处当前最长公共子序列长度，另一个存储在(i,j)处的回溯方向。

相对于算法导论的版本，增加了一个多分支回溯，即存储回溯方向时出现了向上向左都可以的情况时，这时候就代表可能有多个最长公共子序列。当回溯到这里时，让程序带着存储已经回溯的字符串的栈进行递归求解，当走到左上角的时候输出出来

 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# coding=utf-8

class LCS():
    def input(self, x, y):
    #读入待匹配的两个字符串
        if type(x) != str or type(y) != str:
            print 'input error'
            return None
        self.x = x
        self.y = y

    def Compute_LCS(self):
        xlength = len(self.x)
        ylength = len(self.y)
        self.direction_list = [None] * xlength #这个二维列表存着回溯方向
        for i in xrange(xlength):
            self.direction_list[i] = [None] * ylength
        self.lcslength_list = [None] * (xlength + 1)      
        #这个二维列表存着当前最长公共子序列长度
        for j in xrange(xlength + 1):
            self.lcslength_list[j] = [None] * (ylength + 1)

        for i in xrange(0, xlength + 1):
            self.lcslength_list[i][0] = 0
        for j in xrange(0, ylength + 1):
            self.lcslength_list[0][j] = 0
        #下面是进行回溯方向和长度表的赋值
        for i in xrange(1, xlength + 1):
            for j in xrange(1, ylength + 1):
                if self.x[i - 1] == self.y[j - 1]:
                    self.lcslength_list[i][j] = self.lcslength_list[i - 1][j - 1] + 1
                    self.direction_list[i - 1][j - 1] = 0  # 左上
                elif self.lcslength_list[i - 1][j] > self.lcslength_list[i][j - 1]:
                    self.lcslength_list[i][j] = self.lcslength_list[i - 1][j]
                    self.direction_list[i - 1][j - 1] = 1  # 上
                elif self.lcslength_list[i - 1][j] < self.lcslength_list[i][j - 1]:
                    self.lcslength_list[i][j] = self.lcslength_list[i][j - 1]
                    self.direction_list[i - 1][j - 1] = -1  # 左
                else:
                    self.lcslength_list[i][j] = self.lcslength_list[i - 1][j]
                    self.direction_list[i - 1][j - 1] = 2  # 左或上
        self.lcslength = self.lcslength_list[-1][-1]
        return self.direction_list, self.lcslength_list

    def printLCS(self, curlen, i, j, s):
        if i == 0 or j == 0:
            return None

        if self.direction_list[i - 1][j - 1] == 0:
            if curlen == self.lcslength:
                s += self.x[i - 1]
                for i in range(len(s)-1,-1,-1):
                    print s[i],
                print '\n'
            elif curlen < self.lcslength:
                s += self.x[i-1]
                self.printLCS(curlen + 1, i - 1, j - 1, s)
        elif self.direction_list[i - 1][j - 1] == 1:
            self.printLCS(curlen,i - 1, j,s)
        elif self.direction_list[i - 1][j - 1] == -1:
            self.printLCS(curlen,i, j - 1,s)
        else:
            self.printLCS(curlen,i - 1, j,s)
            self.printLCS(curlen,i, j - 1,s)


    def returnLCS(self):
        #回溯的入口
        self.printLCS(1,len(self.x), len(self.y),'')


if __name__ == '__main__':
    p = LCS()
    p.input('abcbdab', 'bdcaba')
    p.Compute_LCS()
    p.returnLCS()

在对’abcbdab’和’bdcaba’两个串用LCS后，得到下面结果：

文章目录