Python 最长公共子串算法,python串算法,[Python]代码#!
Python 最长公共子串算法,python串算法,[Python]代码#!
[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')
相关内容
- Python 实现enum的功能,python实现enum,[Python]代码cl
- Python viterbi算法,pythonviterbi算法,[Python]代码de
- python 中文分词——FMM算法,,[Python]代码im
- Python 设置检查点简单实现,python检查,[Python]代码#
- Python 126邮箱自动登录程序,python126,[Python]代码im
- Python 将阿拉伯数字转换为罗马数字,python阿拉伯,[Pyt
- Python 将罗马数字转换成普通的阿拉伯数字,python阿拉伯
- Python 写入数据到MP3文件中,pythonmp3,[Python]代码wr
- Python 分割文件以及合并文件,python分割,[Python]代码#!
- Python 调用默认浏览器,python调用浏览器,[Python]代码im
评论关闭