最長非連続公共サブストリップアルゴリズムLCSを求めて

pythonは最長の非連続公共サブストリングアルゴリズムLCSを求めます.
動的計画は、最長の非連続的な公共サブストリングアルゴリズムLCS参照アルゴリズムURL:http://blog.chinaunix.net/u1/35100/showart_415862.エントリ:2つの比較すべきシリアルS 1、S 2のリターン:最長の非連続的な共通サブストリング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