`
- 浏览:
1310039 次
- 性别:
- 来自:
江苏
-
感觉用来匹配相似文件比最短编辑距离更靠谱,最短编辑应该是用来纠错的
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.cpp"文件中,很可能包含了C++实现的LCS算法。通常,这种实现会包括一个函数,如`int lcs(string X, string Y)`,该函数接收两个字符串参数,返回它们的最长公共子序列的长度。此外,可能还有一个辅助...
在编程领域,最长公共子串(Longest Common Substring,LCS)问题是一个经典的问题,主要涉及字符串处理和算法设计。在这个案例中,我们关注的是一个由C#实现的自创算法来解决这个问题。下面将详细讲解这个算法的...
Python中最长公共子串(Longest Common Substring, LCS)算法是一种寻找两个字符串共同子序列中长度最长的那个子串的方法。在本实例中,我们关注的是如何使用Python编写一个算法来实现这一功能。 首先,我们要了解...
在本压缩包文件"**LCS.rar**"中,包含了一个名为"**最长公共子序列(LCS)算法**"的程序,它实现了动态规划的方法来寻找两个序列之间的最长公共子序列。动态规划是解决此类问题的一种高效策略,它通过将大问题分解为...
标题"LCS.rar_LCS_Lcs.rar_公共子序列_动态规划"中,"LCS"代表最长公共子序列(Longest Common Subsequence),这是一个经典的计算机科学问题,特别是在算法和数据结构领域。它涉及到找到两个或更多序列中最长的子...
### 动态规划:最长公共子串 LCS #### 长度与定义 **最长公共子串(Longest Common Substring, LCS)**是两个或多个字符串中的最长字符串,该字符串同时也是这些字符串的子串。这里需要注意区分子串与子序列的概念...
最长公共子串(Longest Common Substring,LCS)是一个在计算机科学中常见的字符串处理问题,它涉及到查找两个或多个字符串中的最长连续子序列,这个子序列同时存在于所有字符串中。MFC,全称为Microsoft Foundation...
c源码编写的求两个字符串的最长公共子串,采用递归算法
总结一下,这个压缩包文件"LCS.rar"包含了一个使用C++实现的KMP算法,用于解决最长公共子序列问题。这涉及到了字符串处理、动态规划和高效的查找策略等重要计算机科学概念。为了深入理解这个程序的工作原理,你需要...
这个算法是针对寻找两个字符串的最长公共子串问题的高效解决方案,它在Go语言环境下进行了优化,旨在提供更快的执行速度。 **最长公共子串(Longest Common Substring, LCS)** 最长公共子串问题是指给定两个字符...
最长公共子序列(Longest Common Subsequence, ...总结来说,"LCS.rar"提供了一个C++实现的LCS算法,可以用于解决比较两个序列中最长共享部分的问题。配合MATLAB,我们可以进行算法验证、性能分析和进一步的科学研究。
在编程领域,最长公共子串(Longest Common Substring,LCS)问题是一个经典的问题,它寻找两个或多个字符串中的最长连续子序列,这个子序列同时存在于所有字符串中。在这个问题中,我们专注于PHP如何解决两个字符串...
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
如果两个字符串的首字符不相等,则用三种对齐策略分别计算可能的最长公共子串,然后取最长的一个与当前已知的最长公共子串比较,如果比当前已知的最长公共子串长就用计算出的最长公共子串代替当前已知的最长公共子串...
本压缩包文件“LCS.rar”包含了一个优化后的LCS算法实现,主要关注算法的效率提升以及结果的输出。文件“lcs.cpp”是C++实现的源代码,而“positiongdm”可能是输出的矩阵或结果数据。 LCS问题的基本定义是:给定两...
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
最长公共子序列是指两个序列中没有重复字符的最长子串,它不考虑序列中元素的相对位置,只关心子序列本身的长度。例如,序列"AABCDEF"和"ABDEFGH"的最长公共子序列是"ABD"。 解决LCS问题,通常采用动态规划的方法。...
最长公共子序列(Longest Common Subsequence, LCS)是计算机科学中一种经典的字符串问题,尤其在算法设计和分析中占有重要地位。这个问题的目标是找到两个或多个序列的最长子序列,这个子序列并不需要在原序列中...