求最长非连续公共子串算法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