快捷導(dǎo)航

詳解Python最長(zhǎng)公共子串和最長(zhǎng)公共子序列的實(shí)現(xiàn)

更新時(shí)間：2018年07月07日 14:34:46 作者：wateryouyo的博客

這篇文章主要介紹了詳解Python最長(zhǎng)公共子串和最長(zhǎng)公共子序列的實(shí)現(xiàn)。小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧

最長(zhǎng)公共子串(The Longest Common Substring)

LCS問題就是求兩個(gè)字符串最長(zhǎng)公共子串的問題。解法就是用一個(gè)矩陣來(lái)記錄兩個(gè)字符串中所有位置的兩個(gè)字符之間的匹配情況，若是匹配則為1,否則為0。然后求出對(duì)角線最長(zhǎng)的1的序列，其對(duì)應(yīng)的位置就是最長(zhǎng)匹配子串的位置。

def find_lcsubstr(s1, s2): 
 m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩陣，為方便后續(xù)計(jì)算，比字符串長(zhǎng)度多了一列
 mmax=0  #最長(zhǎng)匹配的長(zhǎng)度
 p=0 #最長(zhǎng)匹配對(duì)應(yīng)在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  #返回最長(zhǎng)子串及其長(zhǎng)度
 
print find_lcsubstr('abcdfg','abdfg')

運(yùn)行得到輸出：('dfg',3)

最長(zhǎng)公共子序列 (The Longest Common Subsequence)

子串要求字符必須是連續(xù)的，但是子序列就不是這樣。最長(zhǎng)公共子序列是一個(gè)十分實(shí)用的問題，它可以描述兩段文字之間的“相似度”，即它們的雷同程度，從而能夠用來(lái)辨別抄襲。對(duì)一段文字進(jìn)行修改之后，計(jì)算改動(dòng)前后文字的最長(zhǎng)公共子序列，將除此子序列外的部分提取出來(lái)，這種方法判斷修改的部分，往往十分準(zhǔn)確。
解法就是用動(dòng)態(tài)回歸的思想，一個(gè)矩陣記錄兩個(gè)字符串中匹配情況，若是匹配則為左上方的值加1，否則為左方和上方的最大值。一個(gè)矩陣記錄轉(zhuǎn)移方向，然后根據(jù)轉(zhuǎn)移方向，回溯找到最長(zhǎng)子序列。

import numpy
def find_lcseque(s1, s2): 
 # 生成字符串長(zhǎng)度加1的0矩陣，m用來(lái)保存對(duì)應(yīng)位置匹配的結(jié)果
 m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ] 
 # d用來(lái)記錄轉(zhuǎn)移方向
 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]: #左值大于上值，則該位置的值為左值，并標(biāo)記回溯時(shí)的方向
  m[p1+1][p2+1] = m[p1+1][p2] 
  d[p1+1][p2+1] = 'left'     
  else:              #上值大于左值，則該位置的值為上值，并標(biāo)記方向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時(shí)
 c = d[p1][p2]
 if c == 'ok':  #匹配成功，插入該字符，并向左上角找下一個(gè)
  s.append(s1[p1-1])
  p1-=1
  p2-=1 
 if c =='left': #根據(jù)標(biāo)記，向左找下一個(gè)
  p2 -= 1
 if c == 'up':  #根據(jù)標(biāo)記，向上找下一個(gè)
  p1 -= 1
 s.reverse() 
 return ''.join(s) 
print find_lcseque('abdfg','abcdfg')

得到輸出結(jié)果：