`
dqifa
  • 浏览: 111463 次
社区版块
存档分类
最新评论

求最长非连续公共子串算法LCS

阅读更多

python 求最长非连续公共子串算法LCS

动态规划求最长非连续公共子串算法LCS
参照算法网址:http://blog.chinaunix.net/u1/35100/showart_415862.html
入口: 两个 要比较的串 S1,S2
返回 : 最长非连续公共子串 S

#coding=gbk
#
class TEMT:
      L,IX1,IX2 =0,0,0

def WLCS( s1,s2 ):
    n1 = len( s1 )
    n2 = len( s2 )
    if n1==0 or n2==0:
        return ""
    MM = [ [ TEMT() for j in range(0,n2 ) ] for I in range(0,n1 ) ]
    if s1[0] == s2[0]:
        MM[0][0].L   = 1
        MM[0][0].IX1 = 0 
        MM[0][0].IX2 = 0
    else:
        MM[0][0].L   = 0
        MM[0][0].IX1 = 0 
        MM[0][0].IX2 = 0
    for I in range(1,n1 ):
        MM[I][0].L   = MM[I-1][0].L
        MM[I][0].IX1 = MM[I-1][0].IX1
        MM[I][0].IX2 = 0
        if s2[0] == s1[I]:
            MM[I][0].L = 1
            if MM[I-1][0].L == 0 :
                MM[I][0].IX1 = I
    for I in range(1,n2 ):
        MM[0][I].L   = MM[0][I-1].L 
        MM[0][I].IX2 = MM[0][I-1].IX2
        MM[0][I].IX1 = 0
        if s2[I] == s1[0]:
            MM[0][I].L = 1
            if MM[0][I-1].L == 0 :
                MM[0][I].IX2 = I

   
    for I in range(1,n1): 
        for J in range(1,n2): 
          if s1[I] ==s2[J] :
            MM[I][J].L    = MM[I-1][J-1].L + 1;
            MM[I][J].IX1 = I;
            MM[I][J].IX2 = J;
          elif (MM[I-1][J].L>MM[I][J-1].L):
            MM[I][J].L    = MM[I-1][J].L;
            MM[I][J].IX1 = MM[I-1][J].IX1;
            MM[I][J].IX2 = MM[I-1][J].IX2;
          else:
            MM[I][J].L    = MM[I][J-1].L;
            MM[I][J].IX1 = MM[I][J-1].IX1;
            MM[I][J].IX2 = MM[I][J-1].IX2;
    I = n1-1; J = n2-1 
    LP = MM[I][J].L;
    if LP==0:
         return ""
    S = [ "0" ] * LP
    K = LP 
    while (I>=0) and (J>=0) :
        LP = MM[I][J].L;
        if LP>0 :
          if s1[I]==s2[J]:
              K = K -1
              S[K] = s1[I];
              I =I-1; J = J-1;
          else:
              K1 = MM[I][J].IX1;
              K2 = MM[I][J].IX2;
              I =K1; J =K2;
        else :
            
            break;
    return "".join(S)

s1 ='abcdabd';
s2 ='b666cjabkkkd';    
print( WLCS(s1,s2) )

 

-- 结果 ---

bcabd

 

from:http://hi.baidu.com/jxq61/item/644aaf0d903b84e0f55ba68f

分享到:
评论

相关推荐

    LCS最长公共子串

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

    LCS(longest common substring)算法,即最大公共子串 C实现

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

    Python最长公共子串算法实例

    本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x ...

    最长公共子串MFC实现

    MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单

    深入解析最长公共子串

    题目:如果字符串一的所有字符... 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。完整介绍动态规划将需要很长的篇幅

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

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

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

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

    java笔试题回文子串-LPS-LCS-Algorithm-Analysis:最长公共子串的实现及相关问题

    最长公共子串(LCS)问题是一直使用的经典计算问题。 该项目探索 LCS,它的一个特例,最长回文子串 (LPS) 问题,以及它的概括以及不同的问题域如何影响算法性能。 我对这些问题实施了各种解决方案,讨论了它们的理论...

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

    请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出一个最长公共子串。 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串, 下面的算法是根据网上的java算法由酒逍遥 ...

    C语言求解最长公共子字符串问题及相关的算法分析

    题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将

    LCS动态规划算法实现

    最长公共子串匹配动态规划算法实现,源代码加注释,可运行啊,这描述限定真死板,还20 字符,吃多了啊

    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 第二步:利用上述的公式一,计算第一行 ...

    最长公共子序列

    如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。...本资源编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。

    基于GPU的LCS算法加速机制研究与实现

    协议特征识别技术中用到了一种重要的LCS算法,它是一种字符串比对算法,提取出字符串中的最长连续公共子串。然而,通过理论分析和实验表明:这个查找过程是一个时间复杂度较高的运算过程,如果输入的数据分组比较大...

    我用Python写的一些算法

    使用动态规划的两种方式实现的LCS(最大公共串)(下面的算法都会使用动态规划的两种方式来实现) 加权有向无环图中最短路径和最长路径 背包问题 最长回文子串(lps) ###幂乘:算法复杂度是O(lgn) ##贪心算法 活动...

    利用C语言来求最大连续子序列乘积的方法

    也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的区别:  子串(Substring)是串的一个连续的部分,子序列(Subsequence)则是从不改变序列的

    1_金策_字符串算法选讲.pdf

    在 O(n log n) 时间空间预处理后(或较复杂的 O(n) 时间空间 预处理), 可以 O(1) 回答: 两个子串的最长公共前缀 (LCP)、最 长公共后缀 (LCS)。 对于拥有周期 p 的串 s, LCP(s[1..n], s[1 + p..n]) = n − p。 输入 ...

    多米诺骨牌算法leetcode-Algorithm_and_DS:Algorithm_and_DS

    java中最长的公共子串 最长递增子序列 硬币变化 最大化切割段 使分区相等的子集的最小总和分区 多米诺骨牌放置 逆因子 在旋转列表中找到最大的数字 可整除数 leetcode 332 硬币找零问题 最大积子

    leetcode表现最好的时间段-DP-Interviews:DP-面试

    注意:其中一些问题可以要求最长/最短公共子串/序列的长度/计数,或者也可以要求生成的子串/子序列。 一串问题 (已作为选择最后操作的所有可能间隔中的所有可能削减的一部分发布) 你总是可以找到最长的回文子序列...

    leetcode2-algorithm-problems:来自leetcode的基本算法问题与go解决方案

    leetcode 2 算法 总结leetcode刷题的常见算法 常见的排序算法 二分查找 陷阱雨水 跳跃游戏 - II 机器人行走 堆栈实现 计算器(整数) ...LCS(最长公共子串) LD(莱文斯坦距离) DATrie(未完成)

Global site tag (gtag.js) - Google Analytics