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
投稿猜你喜欢
最近听了张江老师的深度学习课程，用Pytorch实现神经网络预测，之前做Titanic生存率预测的时候稍微了解过Tensorflow，听说T- HTTPS简介HTTPS(Hyper Text Transfer Protocol Secure)，是一种基于SSL/TLS的HTTP，所有
- 前言这篇文章主要介绍了Python 字符串去除空格的6种方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，来
- 互斥锁在Golang中，互斥锁（Mutex）是一种基本的同步原语，用于实现对共享资源的互斥访问。互斥锁通过在代码中标记临界区来控制对共享资源
- kNN算法是k-近邻算法的简称，主要用来进行分类实践，主要思路如下：1.存在一个训练数据集，每个数据都有对应的标签，也就是说，我们知道样本集
- 关于Python语言，众说纷纭，但无外乎两种，强大，垃圾。大多数人还是对Python持肯定意见，认为它很强大。前些天和两个的大学同学聊天，一
- 我就废话不多说了，直接上代码吧！import cv2img = cv2.imread("1.jpg")b, g, r =
- logging模块简介Python的logging模块提供了通用的日志系统，可以方便第三方模块或者是应用使用。这个模块提供不同的日志级别，并
- 本文实例讲述了C#简单查询SQLite数据库是否存在数据的方法。分享给大家供大家参考，具体如下：//sqlite数据库驱动组件using S
- 本文实例为大家分享了python tkinter库实现气泡屏保和锁屏的具体代码，供大家参考，具体内容如下显示效果如下：代码： im
- TKinterPython 的 GUI 库非常多，之所以选择 Tkinter，一是最为简单，二是自带库，不需下载安装，随时使用，跨平台兼容性
- 本文实例讲述了Python自动发送邮件的方法。分享给大家供大家参考，具体如下：python发邮件需要掌握两个模块的用法，smtplib和em
- 话说土匪老湿在他的大作 《交互设计之回归篇》 里曝光了上次有意思小组竞赛我们小组分享的话题 “瞬间的快感”，但这一极具噱
- 链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了
- 这篇文章主要介绍了Python input函数使用实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 本文实例讲述了C#操作SQLite数据库之读写数据库的方法。分享给大家供大家参考，具体如下：这里演示读写数据库并在窗体（Form）中显示其数
- 1.思路在网上查找了半天，基本都是提取word中文字的，没有找到可以把word中的图片提取出来的方法。一个巧合的情况下，发现将word的后缀
- 起步Python3 起，str 就采用了 Unicode 编码（注意这里并不是 utf8 编码，尽管 .py 文件默认编码是 utf8 ）。
- 今天继续给大家介绍Python相关知识，本文主要内容是Python asyncio异步编程简单实现。一、asyncio事件循环简介async
- asp之家注：一个取图片尺寸的asp类，支持jpg,gif,png格式的图片文件；读取图片的尺寸其实很有用，当我们在设计一个新闻文章添加页面
