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): 
 # length table: every element is set to zero. 
 m = [ [ 0 for x in s2 ] for y in s1 ] 
 # direction table: 1st bit for p1, 2nd bit for p2. 
 d = [ [ None for x in s2 ] for y in s1 ] 
 # we don't have to care about the boundery check. 
 # 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. 
 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')