python实现最长公共子序列
作者：littlethunder 发布时间：2023-06-14 20:53:42
标签：python,最长公共子序列
最长公共子序列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.递归定义最优值
3.以自底向上大方式计算出最优值
python代码如下：
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('')
运行结果输出如下：
4.根据计算最优值得到的信息，构造最优解
上图是运行结果，第一个矩阵是计算公共子序列长度的，可以看到最长是4；第二个矩阵是构造这个最优解用的；最后输出一个最优解BCBA。
来源：https://％bcnet％/littlethunder/article/details/25637173
0
投稿猜你喜欢
- javascript中要判断一个变量是否为array通常是比较困难的，因为var a = [];alert(t
- 本文实例为大家分享了python实现FTP文件下载功能的具体代码，供大家参考，具体内容如下代码：#-*-coding:utf-8-*- im
下午的时候，配好了OpenCV的Python环境，OpenCV的Python环境搭建。于是迫不及待的想体验一下opencv的人脸识别，如下文- 可以在Mac OS X 10.2.x(“Jaguar”)和以上版本上Mac OS X使用二进制安装软
- 今天无意在坛子里看到这样一个求救帖（这里），看了一下，感觉问题比较好解决。但是问题背后的问题却引起了我的反思。把他的页面整理一下看看（为了便
- 在Google Chrome浏览器出来之前，我一直使用FireFox，因为FireFox的插件非常丰富，更因为FireFox有强大的Fire
- 一、软件测试大型软件系统的开发是一个很复杂的过程，其中因为人的因素而所产生的错误非常多，因此软件在开发过程必须要有相应的质量保证活动，而软件
- <script>function getJsFile(url, callBack){
- argparse介绍 argparse包用于解释命令行参数。这里给出几个常用的方法。# 创建解析器对象# @para： descripti
- 如果用户输入的是直接插入到一个SQL语句中的查询，应用程序会很容易受到SQL注入，例如下面的例子:$unsafe_variable = $_
- 在极坐标中，圆的表示方式为：x=x0+rcosθy=y0+rsinθ圆心为(x0,y0),r为半径，θ为旋转度数，值范围为0-359如果给定
- 问题你想使用原始文件名执行文件的I/O操作，也就是说文件名并没有经过系统默认编码去解码或编码过。解决方案默认情况下，所有的文件名都会根据 s
- 一、导言导语：在计算机进行数据交换时，常常会有一个进制转换的过程，我们知道计算机只认0 和 1.在内存系统中，基本基于二进制进行运算的，但是
- 正则表达式概述正则表达式是一个特殊的字符序列，它能帮助你方便的检查一个字符串是否与某种模式匹配。 Python 自1.5版本起增加了re 模
- 开发环境安装最新版Python下载地址：https://www.python.org/downloads/运行Python1.交互方式运行用
- 目前在网上搜到的利用 PyCharm 调试远程服务器程序的教程大多都是针对 PyCharm 2020、2019，甚至更早版本，PyCharm
- 前言：创建进程池可以形象地理解为创建一个并行的流水线，只需创建一次流水线的消耗，处理接收到的任务的，不使用进程池。 ，浪费时间。中方本来没有
- 打算学习 Python 来做数据分析的你，是不是在开始时就遇到各种麻烦呢？到底该装 Python2 呢还是 Python3 ？为什么安装 P
- 安装了pycharm之后有一个新装的python解释器，顶替了之前系统的python那样的话，原来利用pip安装的一些库会无法import.
- import os os.os.listdir(path) 然后再一个一个的分析文件和目录 通过和dos命令dir的巧妙结合，可以很轻松的做
