返回信息流重新拿起数据结构书，看不懂上面的kmp，自己按思路写了个，大致思路是比较模式串的前缀和后缀，计算一个位置不匹配时模式串相对主串的位移，不知道对不对，如果对，和课本上的区别大么？
def getmoveval(pattern):
l=len(pattern)
position=[0]*l
moveval=[0]*l
j=0
for i in range(0,l):
if i == 0:
position[i]=0
moveval[i]=1#moveval是当某位置不匹配时，模式串相对主串右移的距离
else:
if pattern[i]==pattern[j]:
position[i]=j+1
j=j+1
moveval[i]=i-position[i-1]
else:
position[i]=0
moveval[i]=i-position[i-1]
j=0
return moveval
def kmp(main,pattern):
l = len(main)
moveval = getmoveval(pattern)
result = []
i = 0 #模式串相对主串位置
j = 0 #模式串游标
p = 0#主串游标
while i<l:
if main[i+p]==pattern[j]:#一个位置匹配
if j == len(pattern)-1:#若已是最后一个字符
result.append(i)
j = 0
i=i+1
p = 0
else:
p=p+1#游标后移
j=j+1
else:#不匹配
i = i + moveval[j] #模式串右移
p = 0 #游标归零
j = 0
return result
main ="BBC ABCDAB ABCDABCDABDE"
pattern ="ABDE"
print getmoveval(pattern)
print kmp(main,pattern)
求指教
这是一条镜像帖。来源：北邮人论坛 / python / #1381同步于 2014/7/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Python机器人发帖
[虚心求教]自己实现的kmp算法不知对不对
xiao0xiao
2014/7/1镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
http://sincebelieve.com/p/kmp.html
换成 python 大概是这样的：
import sys
def kmp_preprocess(word):
i = 0
j = -1
fail = [-1] * ( len(word) + 1 )
while i < len(word):
while j >= 0 and word[i] != word[j]:
j = fail[j]
i += 1
j += 1
fail[i] = j
return fail
def kmp_search(text, word, fail):
i = 0
j = 0
while i < len(text):
while j >= 0 and text[i] != word[j]:
j = fail[j]
i += 1
j += 1
if j == len(word):
print('Found at %d' % (i - j))
j = fail[j]
if __name__ == '__main__':
fail = kmp_preprocess(sys.argv[2])
kmp_search(sys.argv[1], sys.argv[2], fail)
【 在 xiao0xiao 的大作中提到: 】
: 重新拿起数据结构书，看不懂上面的kmp，自己按思路写了个，大致思路是比较模式串的前缀和后缀，计算一个位置不匹配时模式串相对主串的位移，不知道对不对，如果对，和课本上的区别大么？
: def getmoveval(pattern):
: l=len(pattern)
: ...................