python实现求两个字符串的最长公共子串方法

yipeiwu_com5年前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中的第一个最长公共子串(若有重复)

以上这篇python实现求两个字符串的最长公共子串方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

python实现嵌套列表平铺的两种方法

方法一:使用列表推导式 >>> vec = [[1,2,3],[4,5,6],[7,8,9]] >>> get = [num for elem i...

基于Python实现迪杰斯特拉和弗洛伊德算法

图搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法,供大家参考,具体内容如下 Djstela算法 #encoding=UTF-8 MAX=9 ''' Created on 20...

Sanic框架流式传输操作示例

本文实例讲述了Sanic框架流式传输操作。分享给大家供大家参考,具体如下: 简介 Sanic是一个类似Flask的Python 3.5+ Web服务器,它的写入速度非常快。除了Flask...

Python中的zipfile模块使用详解

zip文件格式是通用的文档压缩标准,在ziplib模块中,使用ZipFile类来操作zip文件,下面具体介绍一下: class zipfile.ZipFile(file[, mode[,...

Python实现统计文本文件字数的方法

本文实例讲述了Python实现统计文本文件字数的方法。分享给大家供大家参考,具体如下: 统计文本文件的字数,从当前目录下的file.txt取文件 # -*- coding: GBK...