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设计】。

相关文章

web.py在SAE中的Session问题解决方法(使用mysql存储)

这段时间一直想尝试着在SAE中使用Python,初步选择了Web.py框架做为开发框架,但是可怜SAE上的资料少的可怜,有点问题基本上解决不了,今天解决一个Session在Session...

python实现俄罗斯方块

网上搜到一个Pygame写的俄罗斯方块(tetris),大部分看懂的前提下增加了注释,Fedora19下运行OK的 主程序: #coding:utf8 #! /usr/bin/env...

python使用itchat库实现微信机器人(好友聊天、群聊天)

itchat是一个开源的微信个人号接口,可以使用该库进行微信网页版中的所有操作,比如:所有好友、添加好友、拉好友群聊、微信机器人等等。详细用户请看文档介绍,在这里。 本文主要使用该库完成...

Windows下Python使用Pandas模块操作Excel文件的教程

Windows下Python使用Pandas模块操作Excel文件的教程

安装Python环境 ANACONDA是一个Python的发行版本,包含了400多个Python最常用的库,其中就包括了数据分析中需要经常使用到的Numpy和Pandas等。更重要的是,...

numpy.transpose对三维数组的转置方法

如下所示: import numpy as np 三维数组 arr1 = np.arange(16).reshape((2, 2, 4)) #[[[ 0 1 2 3] #...