玩蛇网提供最新Python编程技术信息以及Python资源下载!
python零基础培训
您现在的位置: 玩蛇网首页 > Python源码实例 > 正文内容

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') 

站长推荐阅读相关内容:
linux基础入门教程

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


微信扫描下图可直接关注Python公众号

玩蛇网Python QQ群,欢迎加入: ① 279974227 玩蛇网Python新手群
修订日期:2016年01月29日 - 21时30分45秒 发布自玩蛇网

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

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules