Python最长公共子串算法实例
作者:Sephiroth 发布时间:2022-08-11 01:29:57
标签:Python,算法
本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下:
#!/usr/bin/env python
# find an LCS (Longest Common Subsequence).
# *public domain*
def find_lcs_len(s1, s2):
m = [ [ 0 for x in s2 ] for y in s1 ]
for p1 in range(len(s1)):
for p2 in range(len(s2)):
if s1[p1] == s2[p2]:
if p1 == 0 or p2 == 0:
m[p1][p2] = 1
else:
m[p1][p2] = m[p1-1][p2-1]+1
elif m[p1-1][p2] < m[p1][p2-1]:
m[p1][p2] = m[p1][p2-1]
else: # m[p1][p2-1] < m[p1-1][p2]
m[p1][p2] = m[p1-1][p2]
return m[-1][-1]
def find_lcs(s1, s2):
# length table: every element is set to zero.
m = [ [ 0 for x in s2 ] for y in s1 ]
# direction table: 1st bit for p1, 2nd bit for p2.
d = [ [ None for x in s2 ] for y in s1 ]
# we don't have to care about the boundery check.
# a negative index always gives an intact zero.
for p1 in range(len(s1)):
for p2 in range(len(s2)):
if s1[p1] == s2[p2]:
if p1 == 0 or p2 == 0:
m[p1][p2] = 1
else:
m[p1][p2] = m[p1-1][p2-1]+1
d[p1][p2] = 3 # 11: decr. p1 and p2
elif m[p1-1][p2] < m[p1][p2-1]:
m[p1][p2] = m[p1][p2-1]
d[p1][p2] = 2 # 10: decr. p2 only
else: # m[p1][p2-1] < m[p1-1][p2]
m[p1][p2] = m[p1-1][p2]
d[p1][p2] = 1 # 01: decr. p1 only
(p1, p2) = (len(s1)-1, len(s2)-1)
# now we traverse the table in reverse order.
s = []
while 1:
print p1,p2
c = d[p1][p2]
if c == 3: s.append(s1[p1])
if not ((p1 or p2) and m[p1][p2]): break
if c & 2: p2 -= 1
if c & 1: p1 -= 1
s.reverse()
return ''.join(s)
if __name__ == '__main__':
print find_lcs('abcoisjf','axbaoeijf')
print find_lcs_len('abcoisjf','axbaoeijf')
希望本文所述对大家的Python程序设计有所帮助。
0
投稿
猜你喜欢
- Python SMTP发送邮件SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址
- 1.引言效果图:ISBN查询工具通常用于图书管理、图书销售、图书收集和阅读等场景。以下是一些具体的应用场景:图书管理系统:ISBN查询工具可
- 1.在html页面中导入js文件和css文件<link rel="stylesheet" href=".
- 输入汉字提示拼音,试试下面这个函数,不知是不是你要的那个:查询汉字便宜到词典网<%function getpychar(ch
- 本文实例讲述了Python实现PS图像调整黑白效果。分享给大家供大家参考,具体如下:这里用Python 实现 PS 里的图像调整–黑白,PS
- 一、必要的 python 模块PyTorch 的 Vision 模块提供了图像变换的很多函数.torchvision/transforms/
- Access保留字&变量名列表,建表时应避免使用这些词汇和符号。Access 2002/2003-A &nbs
- 今天我要讲如何远程调试openstack。首先我们使用的工具是Pycharm.1.首先介绍一下环境我的openstack是使用rdo一键安装
- 非常好的一篇技术文档,翻译自Louis Lazaris 2009年9月15日发表的《The Z-Index CSS Property: A
- 这篇文章主要介绍了Python tkinter三种布局实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- mysql安装目录使用MySQL AB's Linux RPM分发进行安装后,将在以下系统目录产生文件目录目录内容/usr/bin客
- xbox series和ps5发售以来,国内黄牛价格一直居高不下。虽然海外amazon上ps5补货很少而且基本撑不过一分钟,但是xbox s
- “你如何为成千上万的用户和页面提供CSS?” 这是Nicole Sullivan在她的在丹佛的Web Directions North 大会
- 目录前言环境依赖代码前言本文主要分享一个可以将图片或者视频模糊化的工具代码。技术路线主要是使用ffmpeg滤镜。环境依赖ffmpeg环境部署
- 今天在做sql Server 2005的实验的时候碰到的问题,问题描述很清楚,怀疑是我以前给计算机修改了名称而导致的.可以用select @
- 本文实例讲述了Python实现快速排序的方法。分享给大家供大家参考,具体如下:说起快排的Python实现,首先谈一下,快速排序的思路:1、取
- 尽管很多 NoSQL 数据库近几年大放异彩,但是像 MySQL 这样的关系型数据库依然是互联网的主流数据库之一,每个学 Python 的都有
- 或许你已经看过很多关于CSS3动画的技术,包括前端观察之前发表的一些,那么现在就情看一看CSS3动画的魅力吧。这里是一辑47个令人瞠目结舌的
- 前言保留小数位是我们经常会碰到的问题,尤其是刷题过程中。那么在python中保留小数位的方法也非常多,但是笔者的原则就是什么简单用什么,因此
- 内容摘要:当我们不想让某IP服务我们的网站时,我们就要写段程序来限制IP地址。asp中如何对ip进行过滤限制?本文介绍了一种方法,这个函数只