Python最长公共子串算法实例

时间:2021-11-21 02:06:16

本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下:

  1. #!/usr/bin/env python  
  2. # find an LCS (Longest Common Subsequence).  
  3. # *public domain*  
  4.    
  5. def find_lcs_len(s1, s2):  
  6.  m = [ [ 0 for x in s2 ] for y in s1 ]  
  7.  for p1 in range(len(s1)):  
  8.   for p2 in range(len(s2)):  
  9.    if s1[p1] == s2[p2]:  
  10.     if p1 == 0 or p2 == 0:  
  11.      m[p1][p2] = 1 
  12.     else:  
  13.      m[p1][p2] = m[p1-1][p2-1]+1 
  14.    elif m[p1-1][p2] < m[p1][p2-1]:  
  15.     m[p1][p2] = m[p1][p2-1]  
  16.    else:               # m[p1][p2-1] < m[p1-1][p2]  
  17.     m[p1][p2] = m[p1-1][p2]  
  18.  return m[-1][-1]  
  19.    
  20. def find_lcs(s1, s2):  
  21.  # length table: every element is set to zero.  
  22.  m = [ [ 0 for x in s2 ] for y in s1 ]  
  23.  # direction table: 1st bit for p1, 2nd bit for p2.  
  24.  d = [ [ None for x in s2 ] for y in s1 ]  
  25.  # we don't have to care about the boundery check.  
  26.  # a negative index always gives an intact zero.  
  27.  for p1 in range(len(s1)):  
  28.   for p2 in range(len(s2)):  
  29.    if s1[p1] == s2[p2]:  
  30.     if p1 == 0 or p2 == 0:  
  31.      m[p1][p2] = 1 
  32.     else:  
  33.      m[p1][p2] = m[p1-1][p2-1]+1 
  34.     d[p1][p2] = 3          # 11: decr. p1 and p2  
  35.    elif m[p1-1][p2] < m[p1][p2-1]:  
  36.     m[p1][p2] = m[p1][p2-1]  
  37.     d[p1][p2] = 2          # 10: decr. p2 only  
  38.    else:               # m[p1][p2-1] < m[p1-1][p2]  
  39.     m[p1][p2] = m[p1-1][p2]  
  40.     d[p1][p2] = 1          # 01: decr. p1 only  
  41.  (p1, p2) = (len(s1)-1, len(s2)-1)  
  42.  # now we traverse the table in reverse order.  
  43.  s = []  
  44.  while 1:  
  45.   print p1,p2  
  46.   c = d[p1][p2]  
  47.   if c == 3: s.append(s1[p1])  
  48.   if not ((p1 or p2) and m[p1][p2]): break 
  49.   if c & 2: p2 -= 1 
  50.   if c & 1: p1 -= 1 
  51.  s.reverse()  
  52.  return ''.join(s)  
  53.    
  54. if __name__ == '__main__':  
  55.  print find_lcs('abcoisjf','axbaoeijf')  
  56.  print find_lcs_len('abcoisjf','axbaoeijf'

希望本文所述对大家的Python程序设计有所帮助。