最长公共子序列(LCS)

2019-04-11 10:34:24来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

【问题】 求两字符序列的最长公共字符子序列

 1 def lcs_length(x,y):
 2     m = len(x)
 3     n = len(y)
 4     c = [[0 for _ in range(n+1)] for _ in range(m+1)]
 5     for i in range(1,m+1):
 6         for j in range(1,n+1):
 7             if x[i-1] == y[j-1]:
 8                 c[i][j] = c[i-1][j-1] + 1
 9             else:
10                 c[i][j] = max(c[i-1][j],c[i][j-1])
11     return c[m][n]
12 
13 def lcs(x,y):
14     m = len(x)
15     n = len(y)
16     c = [[0 for _ in range(n+1)] for _ in range(m+1)]
17     b = [[0 for _ in range(n+1)] for _ in range(m+1)]
18     for i in range(1,m+1):
19         for j in range(1,n+1):
20             if x[i-1] == y[j-1]:
21                 c[i][j] = c[i-1][j-1] +1
22                 b[i][j] = 1
23             elif c[i-1][j] > c[i][j-1]:
24                 c[i][j] = c[i-1][j]
25                 b[i][j] = 2
26             else:
27                 c[i][j] = c[i][j-1]
28                 b[i][j] = 3
29     return c[m][n],b 
30 
31 def lcs_trackback(x,y):
32     c,b = lcs(x,y)
33     i = len(x)
34     j = len(y)
35     res = []
36     while i>0 and j>0:
37         if b[i][j] == 1:  #来自左上方=>匹配
38             res.append(x[i-1])
39             i-=1
40             j-=1
41         elif b[i][j] == 2:#来自于上方=>不匹配
42             i-=1
43         else: #==3来自于左方=>不匹配
44             j-=1
45     return "".join(reversed(res))
View Code

 


原文链接:https://www.cnblogs.com/steven2020/p/10664501.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:数据类型之题型

下一篇:使Python中的turtle模块画图两只小羊