python版kmp

ネット上のkmp原理の紹介:マッチングに失敗した時の最も適切なロールバック位置を見つけて、簡単なロールバックからサブ列の最初の文字(従来の列挙検索方式は、簡単なロールバックからサブ列の最初の文字)ではなく、検索の効率を高めることができる.従って、この適切な位置を見つけるために、サブ列を先に処理し、ロールバック位置の配列を得る.
原理を理解して、コードを書きます.python実装
 
コードは次のとおりです.

# -*- coding: cp936 -*-
#---------------------------------------------
#                                            -
#author  chile                            -
#version 1.0                               -
#since                                       -
#date  2014-02-17                                      -
#desc kmp                                            -
#                                            -
#                                            -
#                                            -
#---------------------------------------------

#        ，              
def preprocess(patter):
    length = len(patter)
    p = handlerList(length)
    j = -1
    p[0] = j 
    for i in range(1,length):
        j = p[i - 1]
        while j >= 0 and patter[i] != patter[j+1]:
            j = p[j]
        
        if patter[i] == patter[j+1]: #       ，     +1
            p[i] = j + 1
        else:
            p[i] = -1
    
    return p

#       
def handlerList(len,default = 0):
    if len <= 0:
        return
    p = []
    for i in range(len):
        p.append(default)
    return p

def kmp(value,pattern):
    srcSize = len(value)
    subSize = len(pattern)
    p = preprocess(pattern)
    tIndex , pIndex ,total = 0 , 0 , 0
    while tIndex < srcSize and pIndex < subSize: #         
        if (value[tIndex] == pattern[pIndex]):
            tIndex += 1
            pIndex += 1
        elif pIndex == 0:
            tIndex += 1
        else:
            pIndex = p[pIndex - 1] + 1
       
        if pIndex == subSize:  #      ，         
            pIndex = 0
            total += 1
            print 'find',pattern,'at',(tIndex - subSize)
    print 'find times ' , total

    
var = 'abadfafdewefwfafd'
pattern ='afd'
kmp(var,pattern)