Python最长公共子串算法实例

本文实例讲述了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程序设计有所帮助。