`
- 浏览:
1290094 次
- 性别:
- 来自:
江苏
-
感觉用来匹配相似文件比最短编辑距离更靠谱,最短编辑应该是用来纠错的
http://www.unixuser.org/~euske/python/
这个网站还有不少好脚本
http://www.unixuser.org/~euske/python/lcs.py
zuroc@frodo ~/dev/douban $ cat lcs.py
#!/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')
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
最长公共子序列算法LCS实现。任意输入两个字符串,通过此算法可以找到最长的公共子序列。
c源码编写的求两个字符串的最长公共子串,采用递归算法
使用动态规划方法,实现了最长公共子序列算法,并对动态规划方法作了时间和空间的改进
本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x ...
MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
动态规划解决LCS
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
KMP算法实现最长公共子序列的C++算法
在C++环境下开发的最长公共子序列算法,可以下下来试试看
题目:如果字符串一的所有字符... 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。完整介绍动态规划将需要很长的篇幅
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
求解最长公共子序列,要求输入10个字符 ,用C语言
大二课程算法设计技巧与分析的实验,实现最长公共子序列
一、问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子...在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共子串为lo(cnblogs, belong)。 二、求解算法 对于母串X=<x1,x2,⋯,xm
最长公共字串算法,为算法导论上的算法,可以运行,运行时间为O(mn)
算法实现题 最长公共子序列问题 给定两个序列 X = { x1 , x2 , ... , xm } Y = { y1 , y2 , ... , yn } 求X和Y的一个最长公共子序列 举例 X = { a , b , c , b , d , a , b } Y = { b , d , c , a , b , a } 最长...
用于求解两个串的最长公共子序列,输入两个字符串,从中找到最长的公共子序列。
优化的最长公共子序列算法,可以输出优化值得矩阵以及最后结果