我跟随clrs书并碰到“kmp算法”进行字符串匹配。我使用python实现它(原样)。但是,由于某种原因,它似乎不起作用。我的错在哪里?python的KMP算法
的代码如下:
def kmp_matcher(t,p):
n=len(t)
m=len(p)
# pi=[0]*n;
pi = compute_prefix_function(p)
q=-1
for i in range(n):
while(q>0 and p[q]!=t[i]):
q=pi[q]
if(p[q]==t[i]):
q=q+1
if(q==m):
print "pattern occurs with shift "+str(i-m)
q=pi[q]
def compute_prefix_function(p):
m=len(p)
pi =range(m)
pi[1]=0
k=0
for q in range(2,m):
while(k>0 and p[k]!=p[q]):
k=pi[k]
if(p[k]==p[q]):
k=k+1
pi[q]=k
return pi
t = 'brownfoxlazydog'
p = 'lazy'
kmp_matcher(t,p)
你想读'P [-1]'。这似乎并不是故意的。 – user2357112
我也triede与p [0]。但没有运气.. –