最长公共子序列图解、算法实现和复杂度分析

 1 #-*- encoding:utf-8 -*-
 2 import sys
 3 import pdb
 4 
 5 
 6 def lcs(str_a, str_b):
 7     """最长公共子序列
 8     attributes:
 9         str_a: 字符串a
10         str_b: 字符串b
11     return:
12         两个字符串的最长公共子序列内容
13     exception:
14         TypeError
15     """
16 
17     # 异常检测
18     if not isinstance(str_a, basestring) or not isinstance(str_b, basestring):
19         raise TypeError("Input must be string!")
20 
21     # 定义lcs记录矩阵
22     matrix = [["" for j in range(len(str_b) + 1)] for i in range(len(str_a) + 1)]
23     
24     for i in range(1, len(str_a) + 1):
25         for j in range(1, len(str_b) + 1):
26             sub_a = matrix[i - 1][j] # 上方单元格
27             sub_b = matrix[i][j - 1] # 左侧单元格
28             sub_a_b = matrix[i - 1][j - 1] 29                 + (str_a[i - 1] if str_a[i - 1] == str_b[j - 1] else "") # 左上单元格
30 
31             # 记录下最长的字符串
32             tmp_str = sub_a if len(sub_a) > len(sub_b) else sub_b
33             matrix[i][j] = tmp_str if len(tmp_str) > len(sub_a_b) else sub_a_b
34 
35     return matrix[-1][-1]
36 
37 
38 def main(str_a, str_b):
39     ret = lcs(str_a, str_b)
40     print("lcs=%s, lcs_length=%s" % (ret, len(ret)))
41 
42 
43 if __name__ == ‘__main__‘:
44     main(sys.argv[1], sys.argv[2])

 1 #-*- encoding:utf-8 -*-
 2 import sys
 3 import pdb
 4 
 5 
 6 def lcs(str_a, str_b):
 7     """最长公共子序列
 8     attributes:
 9         str_a: 字符串a
10         str_b: 字符串b
11     return:
12         两个字符串的最长公共子序列内容
13     exception:
14         TypeError
15     """
16 
17     # 异常检测
18     if not isinstance(str_a, basestring) or not isinstance(str_b, basestring):
19         raise TypeError("Input must be string!")
20 
21     # 只需要定义2行的lcs记录矩阵
22     matrix = [["" for j in range(len(str_b) + 1)] for i in range(2)]
23     curr_i = 1
24 
25     for i in range(1, len(str_a) + 1):
26         for j in range(1, len(str_b) + 1):
27             sub_a = matrix[1 - curr_i][j]
28             sub_b = matrix[curr_i][j - 1]
29             sub_a_b = matrix[1 - curr_i][j - 1] 30                 + (str_a[i - 1] if str_a[i - 1] == str_b[j - 1] else "")
31 
32             # 记录下最长的字符串
33             tmp_str = sub_a if len(sub_a) > len(sub_b) else sub_b
34             matrix[curr_i][j] = tmp_str if len(tmp_str) > len(sub_a_b) else sub_a_b
35         curr_i = 1 - curr_i
36 
37     return matrix[1 - curr_i][-1]
38 
39 
40 def main(str_a, str_b):
41     ret = lcs(str_a, str_b)
42     print("lcs=%s, lcs_length=%s" % (ret, len(ret)))
43 
44 
45 if __name__ == ‘__main__‘:
46     main(sys.argv[1], sys.argv[2])