详解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实现微信自动好友验证,自动回复,发送群聊链接方法

Python实现微信自动好友验证,自动回复,发送群聊链接方法

引言: 一开始二维码加群,但是呢,这个东西隔一段时间会过期,我需要 每隔一段时间去更新二维码,然后当群人数超过100人了,只能邀请进群, 这个时候就需要别人添加我为好友,然后我通过,打开...

python 实现将txt文件多行合并为一行并将中间的空格去掉方法

有一个txt文本如下: 151 151 1234561 156421 214156 1523132 031320 现希望将两行合并为一行,并将中间所有的空格都去掉: (pyth...

python实现最小二乘法线性拟合

python实现最小二乘法线性拟合

本文python代码实现的是最小二乘法线性拟合,并且包含自己造的轮子与别人造的轮子的结果比较。 问题:对直线附近的带有噪声的数据进行线性拟合,最终求出w,b的估计值。 最小二乘法基本...

Python Django 页面上展示固定的页码数实现代码

Python Django 页面上展示固定的页码数实现代码

如果页数太多的话,全部显示在页面上就会显得很冗杂 可以在页面中显示规定的页码数 例如: book_list.html: <!DOCTYPE html> <htm...

Python做智能家居温湿度报警系统

Python做智能家居温湿度报警系统

物联网技术开创了一个智慧城市的新时代,从智能摄像头到部署各种传感器,以此对城市各种数据进行收集,并经云端AI技术处理后,有助于提高对交通和街道等城市公共管理能力;物联网的发展也为智能家居...