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实现求两个字符串的最长公共子串方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python特性语法之遍历、公共方法、引用

    一.遍历 通过for...in...的语法结构,我们可以遍历字符串.列表.元组.字典等数据结构. 1.字符串遍历 a_str = "hello world" for char in a_str: print(char,end=' ') 2.列表遍历 a_list = [1,2,3,4,5] for num in a_list: print(num,end=' ') 3.元组遍历 a_tuple =(1,2,3,4,5) for num in a_tuple: print(num,end

  • 对python的unittest架构公共参数token提取方法详解

    额...每个请求都有token值的传入,但是token非常易变,一旦变化,所有的接口用例都得改一遍token,工作量太大了... 那么有没有一种方法能把token提取出来,作为一个全局变量,作为一个参数,从而牵一发而动全身呢?? 经过探索,具体方案如下 先定义一个全局变量token类型为string 然后把请求链接定义一个变量类型为string 然后定义第三个变量=前两个变量相加 然后requests直接传第三个变量就行了 具体代码如下: class Test(unittest.TestCase

  • python 实现求解字符串集的最长公共前缀方法

    问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只要遍历长度结束或者结束前发现有不相同的即可终止,返回不同位置之前的子序列即可,下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能:求解字符串集的最长公共前缀 ''' def find_longest_prefix(str_li

  • python 公共方法汇总解析

    1.计算长度 value = "wangdianchao" # 计算字符个数(长度) number = len(value) print(number) 2.索引取值 value = "wangdianchao" # 获取value"0"位置的字符 number = value[0] print(number) value = "wangdianchao" # 获取value右侧第一个的字符 number = value[-1

  • python中找出numpy array数组的最值及其索引方法

    在list列表中,max(list)可以得到list的最大值,list.index(max(list))可以得到最大值对应的索引 但在numpy中的array没有index方法,取而代之的是where,其又是list没有的 首先我们可以得到array在全局和每行每列的最大值(最小值同理) >>> a = np.arange(9).reshape((3,3)) >>> a array([[0, 1, 2], [9, 4, 5], [6, 7, 8]]) >>&

  • Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法.分享给大家供大家参考,具体如下: 问题 输入 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列,如果有多个,随意输出1个. 输入示例 belong cnblogs 输出示例 blog 分析 既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法. 以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情

  • 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

  • C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

  • JavaScript自定义函数实现查找两个字符串最长公共子串的方法

    本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= "" ,L1=s1.length,L2=s2.length; if (L1>L2){ var s3=s1;s1=s2,s2=s3,L1=s2.length;} for ( var j=L1;j> 0 ;j--) for ( var i= 0 ;i&

  • Python求两个字符串最长公共子序列代码实例

    一.问题描述 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence).比如字符串1:BDCABA:字符串2:ABCBDAB.则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二.算法求解 这是一个动态规划的题目.对于可用动态规划求解的问题,一般有两个特征:①最优子结构:②重叠子问题 ①最优子结构 设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X

  • Python求一批字符串的最长公共前缀算法示例

    Python求一批字符串的最长公共前缀算法示例

    本文实例讲述了Python求一批字符串的最长公共前缀算法.分享给大家供大家参考,具体如下: 思路一:这个题一拿到手,第一反应就是以第一个字符串strs[0]为标准,如果其他字符串的第一个字符和str[0]的第一个字符串相同,则再比较第二个字符串,以此类推直到出现不同为止. def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not st

  • python 动态规划问题解析(背包问题和最长公共子串)

    python 动态规划问题解析(背包问题和最长公共子串)

    目录 背包问题 最长公共子串 背包问题 现在要往一个可以装4个单位重量的背包里怎么装价值最高:A重量1个单位,价值15:B重量3个单位,价值20:C重量4个重量,价值30 使用动态规划填充空格 class SolutionBag: def valuableBag(self,optionalList,sizeBig): #创建网格 grid = [[0 for i in range(sizeBig+1)] for j in range(len(optionalList)+1)] #从行列序号1开始

  • Python实现求两个csv文件交集的方法

    本文实例讲述了Python实现求两个csv文件交集的方法.分享给大家供大家参考,具体如下: #!/usr/bin/env python rd3 = open('data_17_17_2.csv') base = open('data_17_17_3.csv') wr3 = open('delNoBuyed3DayAndStoreAndInCar4.5.2.csv','w+') bsData = base.readlines() i = 1 for key in rd3: if key in bs

  • Python实现求两个数组交集的方法示例

    本文实例讲述了Python实现求两个数组交集的方法.分享给大家供大家参考,具体如下: 一.题目 给定两个数组,编写一个函数来计算它们的交集. 例1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 例2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [4,9] 说明: 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致 我们可以不考虑输出结果的顺序 二.解法 首先把两个数组都排序,然后两个数

  • java实现字符串匹配求两个字符串的最大公共子串

    java实现字符串匹配求两个字符串的最大公共子串

    本文实例讲述了java实现求两个字符串最大公共子串的方法.分享给大家供大家参考,具体如下: 最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串. 算法思想:基于图计算两字符串的公共子串.具体算法思想参照下图: 输入字符串S1:achmacmh    输入字符串S2:macham 第a步,是将字符串s1,s2分别按字节拆分,构成一个二维数组: 二维数组中的值如b所示,比如第一行第一列的值表示字符串s2和s1的第一个字节是否相等,若相等就是1

  • python实现查找两个字符串中相同字符并输出的方法

    本文实例讲述了python实现查找两个字符串中相同字符并输出的方法.分享给大家供大家参考.具体实现方法如下: seq1 = "spam" seq2 = "scam" res = [] for x in seq1: if x in seq2: res.append(x) print res 输出结果如下: ['s', 'a', 'm'] 希望本文所述对大家的Python程序设计有所帮助.

随机推荐