python实现求两个字符串的最长公共子串方法
作者：chimuuu 发布时间：2021-08-02 21:14:08
标签：python,字符串,子串
如下所示：
# coding:utf-8
'''
求两个字符串的最长公共子串
思想：建立一个二维数组，保存连续位相同与否的状态
'''
def getNumofCommonSubstr(str1, str2):
lstr1 = len(str1)
lstr2 = len(str2)
record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位
maxNum = 0 # 最长匹配长度
p = 0 # 匹配的起始位
for i in range(lstr1):
for j in range(lstr2):
if str1[i] == str2[j]:
# 相同则累加
record[i+1][j+1] = record[i][j] + 1
if record[i+1][j+1] > maxNum:
# 获取最大匹配长度
maxNum = record[i+1][j+1]
# 记录最大匹配长度的终止位置
p = i + 1
return str1[p-maxNum:p], maxNum
if __name__ == '__main__':
str1 = raw_input()
str2 = raw_input()
res = getNumofCommonSubstr(str1, str2)
print res
输出结果：字符串str1中的第一个最长公共子串（若有重复）
来源：https://blog.csdn.net/C_Donald/article/details/77247758
0
投稿猜你喜欢
- 核心提示：VB读取MP3文件帧的信息比特率，采样频率，播放时间Private Sub Command1_Click()On Error Go
前言setTimeout，前端工程师必定会打交道的一个函数。它看上去非常的简单，朴实，有着一个很不平凡的名字--定时器。其实网上关于Java- 在数据处理的时候，尤其在搞大数据竞赛的时候经常会遇到一个问题就是，多个表单的合并问题，比如一个表单有user_id和age这两个字段，另一个
- 有一个ssqdatav2数据，要找到其中的深圳，并且替换成圳。因为收集到的数据出现了错误，本来只有省份简写的地方却出现了深圳。如何找到DF中
- 我们在微博上可以对图片进行向左转向右转等旋转操作，让用户可以从不同的视角欣赏图片效果。本文将结合实例为您讲解如何使用Javascript结合
- 1、创建表 createtableTest_Increase( useridnumber(10)NOTNULLprimarykey,/*主键
- 如何获知用户的IP？<％ Dim ValidLog ' 日志变量 Valid
- 我需要使用tesseract-OCR的模块，vs的配置有点麻烦，所以采用py的环境，搭建。1.在python.org网站下载python3.
- 研究编码，得知GB2312编码与区位码的关系，尝试之后，得此程序。搜索，似乎没人写，故发此地。1.简述（1）GB2312标准的定义，其实就是
- 本文介绍了Vue.js 常用模板语法，分享给大家，具体如下：一、文本渲染Vue支持动态渲染文本，即在修改属性的同时，实时渲染文本内容。同时为
- Urllib官方文档地址：https://docs.python.org/3/library/urllib.htmlurllib提供了一系列
- Python的全局变量：int string， list， dic(map) 如果存在global就能够修改它的值。而不管这个global是
- Django实现内容缓存：1、内存缓存settings.py文件配置CACHES = { 'default':
- <table border="1" id="tab"> <tr>
- 本文实例讲述了Python中shape计算矩阵的方法。分享给大家供大家参考，具体如下：看到机器学习算法时，注意到了shape计算矩阵的方法接
- 在javascript中this的指向一直是前端同事的心头病，也同时是各面试题的首选，现在我们就来总结一下js中this的指向。首先需要了解
- 豆瓣电影排行榜前250 分为10页，第一页的url为https://movie.douban.com/top250,但实际上应该是https
- 外网python2.7 虚拟环境中安装了 flask 模块，期望在内网使用，如何迁移外网的虚拟环境到内网呢？1 进入外网python虚拟环境
- 由于Caffe使用的存储图像的数据库是lmdb，因此有时候需要对lmdb文件进行操作，本文主要讲解如何用Python合并lmdb文件。没有l
- 内容摘要：除了内部性能增强和优化外，IIS6.0版本的 Active Server Pages(ASP)&nb
