python版kmp

15468

　　网上对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 != patter[j+1]:
j = p[j]
if patter == patter[j+1]: #含有重复字符时，回退的位置+1
p = j + 1
else:
p = -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)