玩蛇网提供最新Python编程技术信息以及Python资源下载!
您现在的位置: 玩蛇网首页 > Python源码实例_Python程序源代码_网站项目下载 > 正文内容

Python算法--最长公共子串算法代码讲解

Python入门佳作 经典教程的全新修订 10个项目引人入胜
玩蛇网推荐图文教程:python黑客多线程扫描器

Python如何匹配最长公共子序列算法?本文就为大家提供了关于Python算法--最长公共子串算法代码讲解案例教程。这属于python基础算法、Python字符串处理其中的一项。

如下代码中使用到了python 列表排序中的reverse方法。

Python算法--最长公共子串算法代码讲解,以下代码供大家学习参考使用。

#!/usr/bin/env python
 
# find an LCS (Longest Common Subsequence). 

# *public domain* 

def find_lcs_len(s1, s2): 
  m = [ [ 0 for x in s2 ] for y in s1 ] 
  for p1 in range(len(s1)): 
    for p2 in range(len(s2)): 
      if s1[p1] == s2[p2]: 
        if p1 == 0 or p2 == 0: 
          m[p1][p2] = 1 
        else: 
          m[p1][p2] = m[p1-1][p2-1]+1 
      elif m[p1-1][p2] < m[p1][p2-1]: 
        m[p1][p2] = m[p1][p2-1] 
      else:                             

# m[p1][p2-1] < m[p1-1][p2] 

        m[p1][p2] = m[p1-1][p2] 
  return m[-1][-1] 

def find_lcs(s1, s2):  # 长度表:每个元素被设置为零。 
  
  m = [ [ 0 for x in s2 ] for y in s1 ] # 方向表: 1st bit for p1, 2nd bit for p2. 
  
  d = [ [ None for x in s2 ] for y in s1 ] 
  
  # a negative index always gives an intact zero. 
  for p1 in range(len(s1)): 
    for p2 in range(len(s2)): 
      if s1[p1] == s2[p2]: 
        if p1 == 0 or p2 == 0: 
          m[p1][p2] = 1 
        else: 
          m[p1][p2] = m[p1-1][p2-1]+1 
        d[p1][p2] = 3                   # 11: decr. p1 and p2 
      elif m[p1-1][p2] < m[p1][p2-1]: 
        m[p1][p2] = m[p1][p2-1] 
        d[p1][p2] = 2                   # 10: decr. p2 only 
      else:                             # m[p1][p2-1] < m[p1-1][p2] 
        m[p1][p2] = m[p1-1][p2] 
        d[p1][p2] = 1                   # 01: decr. p1 only 
  (p1, p2) = (len(s1)-1, len(s2)-1) 

# now we traverse the table in reverse order. 
#www.iplaypython.com
  
  s = [] 
  while 1: 
    print p1,p2 
    c = d[p1][p2] 
    if c == 3: s.append(s1[p1]) 
    if not ((p1 or p2) and m[p1][p2]): break 
    if c & 2: p2 -= 1 
    if c & 1: p1 -= 1 
  s.reverse() 
  return ''.join(s) 

if __name__ == '__main__': 
  print find_lcs('abcoisjf','axbaoeijf') 
  print find_lcs_len('abcoisjf','axbaoeijf') 

玩蛇网文章,转载请注明出处和来源网址:http://www.iplaypython.com/code/c2711.html



微信公众号搜索"玩蛇网Python之家"加关注,每日最新的Python资讯、图文视频教程可以让你一手全掌握。强烈推荐关注!

微信扫描下图可直接关注

玩蛇网PythonQQ群,欢迎加入: ① 240764603 玩蛇网Python新手群
出炉日期:2016-01-29 21:30 玩蛇网 www.iplaypython.com

我要分享到:
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules