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生成器用法实例详解

本文实例讲述了python生成器用法。分享给大家供大家参考,具体如下: 1. 生成器 利用迭代器,我们可以在每次迭代获取数据(通过next()方法)时按照特定的规律进行生成。但是我们在实...

Python 查看文件的编码格式方法

在读取中文的情况下,通常会遇到一些编码的问题,但是首先需要了解目前的编码方式是什么,然后再用decode或者encode去编码和解码,下面是使用chardet库来查看编码方式的。 i...

Python实现的tab文件操作类分享

类代码: # -*- coding:gbk -*- import os class TABFILE: def __init__(self, filename, dest_fi...

如何在python中实现随机选择

这篇文章主要介绍了如何在python中实现随机选择,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 想从一个序列中随机抽取若干元素,或者...

详解使用pymysql在python中对mysql的增删改查操作(综合)

详解使用pymysql在python中对mysql的增删改查操作(综合)

这一次将使用pymysql来进行一次对MySQL的增删改查的全部操作,相当于对前五次的总结: 先查阅数据库: 现在编写源码进行增删改查操作,源码为: #!/usr/bin/py...