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

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

相关文章

Python序列化与反序列化pickle用法实例

这篇文章主要介绍了Python序列化与反序列化pickle用法实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 要将Python对象...

Python3.5内置模块之os模块、sys模块、shutil模块用法实例分析

Python3.5内置模块之os模块、sys模块、shutil模块用法实例分析

本文实例讲述了Python3.5内置模块之os模块、sys模块、shutil模块用法。分享给大家供大家参考,具体如下: 1、os模块:提供对操作系统进行调用的接口 #!/usr/b...

python序列化与数据持久化实例详解

python序列化与数据持久化实例详解

本文实例讲述了python序列化与数据持久化。分享给大家供大家参考,具体如下: 数据持久化的方式有: 1.普通文件无格式写入:将数据直接写入到文件中 2.普通序列化写入:json,pic...

Python数据结构之顺序表的实现代码示例

Python数据结构之顺序表的实现代码示例

顺序表即线性表的顺序存储结构。它是通过一组地址连续的存储单元对线性表中的数据进行存储的,相邻的两个元素在物理位置上也是相邻的。比如,第1个元素是存储在线性表的起始位置LOC(1),那么第...

Python 实现字符串中指定位置插入一个字符

如下所示: str_1='wo shi yi zhi da da niu/n'str_list=list(str_1) nPos=str_list.index('/') str_li...