服务器之家

服务器之家 > 正文

python实现最长公共子序列

时间:2021-02-23 00:19     来源/作者:littlethunder

最长公共子序列python实现,最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来。

1.找出最优解的性质,并刻划其结构特征

序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么a[:m]和b[:n]的最长公共子序列长度就是a[:m-1]和b[:n-1]的最长公共子序列长度+1;如果a[m-1]!=b[n-1],那么a[:m]和b[:n]的最长公共子序列长度就是MAX(a[:m-1]和b[:n]的最长公共子序列长度,a[:m]和b[:n-1]的最长公共子序列长度)。

2.递归定义最优值

python实现最长公共子序列

3.以自底向上大方式计算出最优值

python代码如下:

?
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
def lcs(a,b):
  lena=len(a)
  lenb=len(b)
  c=[[0 for i in range(lenb+1)] for j in range(lena+1)]
  flag=[[0 for i in range(lenb+1)] for j in range(lena+1)]
  for i in range(lena):
    for j in range(lenb):
      if a[i]==b[j]:
        c[i+1][j+1]=c[i][j]+1
        flag[i+1][j+1]='ok'
      elif c[i+1][j]>c[i][j+1]:
        c[i+1][j+1]=c[i+1][j]
        flag[i+1][j+1]='left'
      else:
        c[i+1][j+1]=c[i][j+1]
        flag[i+1][j+1]='up'
  return c,flag
 
def printLcs(flag,a,i,j):
  if i==0 or j==0:
    return
  if flag[i][j]=='ok':
    printLcs(flag,a,i-1,j-1)
    print(a[i-1],end='')
  elif flag[i][j]=='left':
    printLcs(flag,a,i,j-1)
  else:
    printLcs(flag,a,i-1,j)
     
a='ABCBDAB'
b='BDCABA'
c,flag=lcs(a,b)
for i in c:
  print(i)
print('')
for j in flag:
  print(j)
print('')
printLcs(flag,a,len(a),len(b))
print('')

python实现最长公共子序列

运行结果输出如下:

python实现最长公共子序列

4.根据计算最优值得到的信息,构造最优解

上图是运行结果,第一个矩阵是计算公共子序列长度的,可以看到最长是4;第二个矩阵是构造这个最优解用的;最后输出一个最优解BCBA。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/littlethunder/article/details/25637173

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部