gpt4 book ai didi

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

转载 作者:qq735679552 更新时间:2022-09-27 22:32:09 34 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章详解Python最长公共子串和最长公共子序列的实现由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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,否则为左方和上方的最大值。一个矩阵记录转移方向,然后根据转移方向,回溯找到最长子序列.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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最长公共子串和最长公共子序列的实现

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我.

原文链接:https://blog.csdn.net/wateryouyo/article/details/50917812 。

最后此篇关于详解Python最长公共子串和最长公共子序列的实现的文章就讲到这里了,如果你想了解更多关于详解Python最长公共子串和最长公共子序列的实现的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

34 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com