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
投稿
猜你喜欢
- 我就废话不多说,直接上代码吧!# -*- coding: utf-8 -*-import cv2import numpy as npfrom
- 一、概述有时候会在一台主机上安装多个不同的Python版本,用以运行不同时期开发的项目, 而在这些不同的Python版本上有时又会加装不同的
- 我就废话不多说了,还是直接上代码吧!import osimport xml.dom.minidomimport cv2 as cvImgPa
- 如下所示:import osimport timeimport subprocesssubprocess.Popen(r'cmd
- 想要根据django中的模型和配置生成SQL语句,需要先进行一定的设置:首先需要在你的app文件夹中进入setting.py文件,里面有一个
- 一、匹配目标文件中所有以https?://开头,以.jpg|.png|.jpeg结尾的字符串二、尝试过程1) &n
- 问题描述如下:解决方案如下:下图中字体调整为18及以上效果如下:来源:https://blog.csdn.net/appleyuchi/ar
- 客户端程序编写免不了经常接触XMLHttpRequest对象。微软的XHR实现的progid又是一串一串的。 烦人。抽一个中午时间,找了找资
- AES(英文:Advanced Encryption Standard,中文:高级加密标准),是一种区块加密标准。AES将原始数
- 鉴于上一篇中最后三个问题:1、上述程序是否能进行优化(比如功能相同的)2、创建三个3个实例,用了3个语句,能否建一个函数,只输入一个数n,就
- glob 文件名模式匹配,不用遍历整个目录判断每个文件是不是符合。1、通配符星号(*)匹配零个或多个字符import globf
- 网站用户为什么注册?这个问题在平时我们讨论的并不多。我们常常单纯的在设想如何简化注册流程,如何从细节的关怀入手避免用户注册时填写错误信息造成
- 循环是我们经常用到的一个概念,比如,循环计算数字叠加、循环输出文字内容等。循环是运行重复内容的一个最简单的方法,简化了代码流程,增加了时效性
- 在python中读取一个文本文件相信大家都比较熟悉了,但如果我们遇到一个二进制文件要读取怎么办呢?我们尝试使用 Python 中的内置 op
- 通用形态学函数上篇博文,我们介绍了形态学的基础腐蚀与膨胀操作,而将腐蚀与膨胀结合起来进行组合,我们就能实现开运算,闭运算等复杂的形态学运算。
- 本文实例分析了ThinkPHP中的__initialize()和类的构造函数__construct()。分享给大家供大家参考。具体分析如下:
- 一、TensorFlow模型保存和提取方法1. TensorFlow通过tf.train.Saver类实现神经网络模型的保存和提取。tf.t
- 前言今天呢,笔者想和大家聊聊python+pytest接口自动化中将代码进行封装,只有将测试代码进行封装,才能被测试框架识别执行。例如单个接
- Python特别灵活,肯定方法不止一种,这里介绍一种我觉得比较简单的方法。如下图,使用x == np.max(x) 获得一个掩模矩阵,然后使
- 概述很多人接触Python,都是从爬虫开始,其实很多语言都可以做爬虫,只是Python相对其他语言来说,更加简单而已。但是Python并不止