详解Python最长公共子串和最长公共子序列的实现

yipeiwu_com5年前Python基础

最长公共子串(The Longest Common Substring)

LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置。

def find_lcsubstr(s1, s2): 
 m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度多了一列
 mmax=0  #最长匹配的长度
 p=0 #最长匹配对应在s1中的最后一位
 for i in range(len(s1)):
 for j in range(len(s2)):
  if s1[i]==s2[j]:
  m[i+1][j+1]=m[i][j]+1
  if m[i+1][j+1]>mmax:
   mmax=m[i+1][j+1]
   p=i+1
 return s1[p-mmax:p],mmax  #返回最长子串及其长度
 
print find_lcsubstr('abcdfg','abdfg')

运行得到输出:('dfg',3)

最长公共子序列 (The Longest Common Subsequence)

子串要求字符必须是连续的,但是子序列就不是这样。最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。
        解法就是用动态回归的思想,一个矩阵记录两个字符串中匹配情况,若是匹配则为左上方的值加1,否则为左方和上方的最大值。一个矩阵记录转移方向,然后根据转移方向,回溯找到最长子序列。

import numpy
def find_lcseque(s1, s2): 
 # 生成字符串长度加1的0矩阵,m用来保存对应位置匹配的结果
 m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ] 
 # d用来记录转移方向
 d = [ [ None for x in range(len(s2)+1) ] for y in range(len(s1)+1) ] 
 
 for p1 in range(len(s1)): 
 for p2 in range(len(s2)): 
  if s1[p1] == s2[p2]:      #字符匹配成功,则该位置的值为左上方的值加1
  m[p1+1][p2+1] = m[p1][p2]+1
  d[p1+1][p2+1] = 'ok'     
  elif m[p1+1][p2] > m[p1][p2+1]: #左值大于上值,则该位置的值为左值,并标记回溯时的方向
  m[p1+1][p2+1] = m[p1+1][p2] 
  d[p1+1][p2+1] = 'left'     
  else:              #上值大于左值,则该位置的值为上值,并标记方向up
  m[p1+1][p2+1] = m[p1][p2+1]  
  d[p1+1][p2+1] = 'up'     
 (p1, p2) = (len(s1), len(s2)) 
 print numpy.array(d)
 s = [] 
 while m[p1][p2]:  #不为None时
 c = d[p1][p2]
 if c == 'ok':  #匹配成功,插入该字符,并向左上角找下一个
  s.append(s1[p1-1])
  p1-=1
  p2-=1 
 if c =='left': #根据标记,向左找下一个
  p2 -= 1
 if c == 'up':  #根据标记,向上找下一个
  p1 -= 1
 s.reverse() 
 return ''.join(s) 
print find_lcseque('abdfg','abcdfg')

得到输出结果:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

zookeeper python接口实例详解

本文主要讲python支持zookeeper的接口库安装和使用。zk的python接口库有zkpython,还有kazoo,下面是zkpython,是基于zk的C库的python接口。...

python求解水仙花数的方法

本文实例讲述了python求解水仙花数的方法。分享给大家供大家参考。具体如下: 一个N位的十进制正整数,如果它的每个位上的数字的N次方的和等于这个数本身,则称其为花朵数。 #!/us...

Python编程实现从字典中提取子集的方法分析

本文实例讲述了Python编程实现从字典中提取子集的方法。分享给大家供大家参考,具体如下: 首先我们会想到使用字典推导式(dictionary comprehension)来解决这个问题...

Python编码类型转换方法详解

本文实例讲述了Python编码类型转换方法。分享给大家供大家参考,具体如下: 1:Python和unicode 为了正确处理多语言文本,Python在2.0版后引入了Unicode字符串...

详解python校验SQL脚本命名规则

详解python校验SQL脚本命名规则

需求背景 检查脚本文件中SQL语句是否按规范编写,规则如下: 创建表时,表名称需以"t_"开头且均为小写 增加和创建列时,列名称均为小写字母和_组成 创建函数,函数名称需以...