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并不止
