在研究sphinx的时候,看到sphinx的排序算法是LCS
于是小研究了一下LCS,原理:
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1序列,其对应的位置就是最长匹配子串的位置.
下面是字符串21232523311324和字符串312123223445的匹配矩阵,前者为X方向的,后者为Y方向的。不难找到,红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为:21232
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量,可以省去这部分时间。下面是新的矩阵生成方式:
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
当字符匹配的时候,我们并不是简单的给相应元素赋上1,而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置,在矩阵生成的过程中来判断当前生成的元素的值是不是最大的,据此来改变标记变量的值,那么到矩阵完成的时候,最长匹配子串的位置和长度就已经出来了。
代码如下:
def LCS(x, y):
print x,y
if (len(x) == 0 or len(y) == 0):
return ""
else:
a = x[0]
b = y[0]
if (a == b):
return LCS(x[1:], y[1:]) + a
else:
return cxMax(LCS(x[1:], y), LCS(x, y[1:]))
def cxMax(a, b):
if (a >= b):
return a
else:
return b
if __name__ == '__main__':
cxStra = "123456789"
cxStrb = "123z"
lista = []
listb = []
for i in range(0, len(cxStra)):
lista.append(cxStra[i])
for i in range(0, len(cxStrb)):
listb.append(cxStrb[i])
d = LCS(lista, listb)
print 'LCS is:%s' % d[::-1]
分享到:
相关推荐
c源码编写的求两个字符串的最长公共子串,采用递归算法
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单
题目:如果字符串一的所有字符... 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。完整介绍动态规划将需要很长的篇幅
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
原理 举例说明:A=GGATCGA,B=GAATTCAGTTA 第一步:初始化LD矩阵 公式一 若ai=bj,则LD(i,j)=LD(i-1,j-1) 若ai≠bj,则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1 第二步:利用上述的公式一,计算第一行 ...
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
一、问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子...在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共子串为lo(cnblogs, belong)。 二、求解算法 对于母串X=<x1,x2,⋯,xm
本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x ...
请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出一个最长公共子串。 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串, 下面的算法是根据网上的java算法由酒逍遥 ...
基于LCS最长公共子串的diff工具, 可比较相同目录结构下的所有文件。
从“公共子串”的角度来分析求解“最长公共子序列”(LCS)
最长公共子串(LCS)问题是一直使用的经典计算问题。 该项目探索 LCS,它的一个特例,最长回文子串 (LPS) 问题,以及它的概括以及不同的问题域如何影响算法性能。 我对这些问题实施了各种解决方案,讨论了它们的理论...
LCS 类比较两个文本文件并找到最长公共子串 (LCS)。 这是通过使用自定义 String 类模拟字符串在旧版本 Java 中的行为方式来实现的 此代码用于通过命令行比较两个文本文件并返回两者共享的最长公共子字符串。 对于这...
最长公共子字符串(LCS)服务器概述构建一个简单的Web应用程序,允许用户在给定字符串列表的情况下请求最长公共子字符串。 功能要求通过HTTP POST解决最长的公共子字符串问题用户应该能够通过向服务器位于...
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。...本资源编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将
最长公共子串匹配动态规划算法实现,源代码加注释,可运行啊,这描述限定真死板,还20 字符,吃多了啊
最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知...