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 write无法写入文件的解决方法

尝试用python写文件,但是无法写入文件,文件内容为空。 原代码片段如下, poem = "This is a poem" dirs = '~/work/python/' #改为...

Python中的rjust()方法使用详解

 rjust()该方法返回字符串合理字符串的右边的长度宽度。填充是通过使用指定的fillchar(默认为空格)。如果宽度小于len(s)返回原始字符串。 语法 以下是rjust...

Python语法快速入门指南

Python语法快速入门指南

Python语言与Perl,C和Java等语言有许多相似之处。但是,也存在一些差异。 在本章中我们将来学习Python的基础语法,让你快速学会Python编程。 第一个Python程序...

python issubclass 和 isinstance函数

Python issubclass() 函数 issubclass() 方法用于判断参数 class 是否是类型参数 classinfo 的子类。 语法: issubclass(...

详解Django中间件执行顺序

详解Django中间件执行顺序

中间件 Django中的中间件是一个轻量级、底层的插件系统,可以介入Django的请求和响应处理过程,修改Django的输入或输出。中间件的设计为开发者提供了一种无侵入式的开发方式,增强...