`

LCS 最长公共子串

阅读更多
在研究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]

分享到:
评论

相关推荐

    LCS最长公共子串

    c源码编写的求两个字符串的最长公共子串,采用递归算法

    最长公共子串MFC实现

    最长公共子串(Longest Common Substring,LCS)是一个在计算机科学中常见的字符串处理问题,它涉及到查找两个或多个字符串中的最长连续子序列,这个子序列同时存在于所有字符串中。MFC,全称为Microsoft Foundation...

    动态规划:最长公共子串 LCS

    ### 动态规划:最长公共子串 LCS #### 长度与定义 **最长公共子串(Longest Common Substring, LCS)**是两个或多个字符串中的最长字符串,该字符串同时也是这些字符串的子串。这里需要注意区分子串与子序列的概念...

    C#最长公共子串(连续)算法(自创)

    在编程领域,最长公共子串(Longest Common Substring,LCS)问题是一个经典的问题,主要涉及字符串处理和算法设计。在这个案例中,我们关注的是一个由C#实现的自创算法来解决这个问题。下面将详细讲解这个算法的...

    PHP实现求两个字符串最长公共子串的方法示例

    在编程领域,最长公共子串(Longest Common Substring,LCS)问题是一个经典的问题,它寻找两个或多个字符串中的最长连续子序列,这个子序列同时存在于所有字符串中。在这个问题中,我们专注于PHP如何解决两个字符串...

    Python最长公共子串算法实例

    Python中最长公共子串(Longest Common Substring, LCS)算法是一种寻找两个字符串共同子序列中长度最长的那个子串的方法。在本实例中,我们关注的是如何使用Python编写一个算法来实现这一功能。 首先,我们要了解...

    算法系列之六:最长公共子序列(LCS)问题(连续子序列)的三种解法.doc

    如果两个字符串的首字符不相等,则用三种对齐策略分别计算可能的最长公共子串,然后取最长的一个与当前已知的最长公共子串比较,如果比当前已知的最长公共子串长就用计算出的最长公共子串代替当前已知的最长公共子串...

    java-diff:根据LCS最长公共子串算法,采用java实现比较文本的不同之处(增加,删除,更新)

    原理 举例说明: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)算法,即最大公共子串 C实现

    LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...

    利用C++实现最长公共子序列与最长公共子串

    一、问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子...在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共子串为lo(cnblogs, belong)。 二、求解算法 对于母串X=<x1,x2,⋯,xm

    PHP实现求解最长公共子串问题的方法

    例如,`LCS::GetRandomStrings`方法可以生成用于测试的随机字符串,而`LCS::main`方法则是算法实现的核心,负责执行动态规划的计算步骤,并最终输出最长公共子串的结果和算法运行时间。通过对算法运行时间的记录,...

    详解Python最长公共子串和最长公共子序列的实现

    LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...

    从“公共子串”的角度来分析求解“最长公共子序列”(LCS)

    而LCS则不同,它不要求连续性,所以 "AE" 也是 "ABCDEF" 和 "ABEFGH" 的一个最长公共子序列,尽管它不是公共子串。 接下来,我们将从算法的角度探讨如何求解LCS。一种常见的方法是使用动态规划,这在计算机科学中是...

    Go-go-lcssGo中的最快公共子串算法

    **最长公共子串(Longest Common Substring, LCS)** 最长公共子串问题是指给定两个字符串,找出它们之间最长的、共同的子串。例如,字符串 "ABCDGH" 和 "AEDFHR" 的最长公共子串是 "ADH"。解决这个问题的算法通常...

    LCS 最长公共子序列 JAVA

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要出现在序列比对、文本编辑距离等领域。在两个给定的字符串中,LCS是指不考虑字符顺序的最长子串,它同时存在于这两个字符...

Global site tag (gtag.js) - Google Analytics