python版kmp
网上对kmp原理的介绍：找到匹配失败时的最合适的回退位置，而不是简单的回退到子串的第一个字符(常规的枚举查找方式，是简单的回退到子串的第一个字符),即可提高查找的效率.因此为了找到这个合适的位置,先对子串预处理,从而得到一个回退位置的数组。
理解原理后，在写代码。python实现
代码如下：
# -*- coding: cp936 -*-
#---------------------------------------------
# -
#authorchile -
#version 1.0 -
#since -
#date2014-02-17 -
#desc kmp查找字符串 -
# -
# -
# -
#---------------------------------------------
#对子串加以预处理，找到匹配失败时子串回退的位置
def preprocess(patter):
length = len(patter)
p = handlerList(length)
j = -1
p = j
for i in range(1,length):
j = p
while j >= 0 and patter != patter:
j = p
if patter == patter: #含有重复字符时，回退的位置+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 == pattern):
tIndex += 1
pIndex += 1
elif pIndex == 0:
tIndex += 1
else:
pIndex = p + 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)
页:
[1]