我跟随clrs的书,遇到了字符串匹配的“kmp算法”。我用python(按原样)实现了它。然而,由于某种原因,它似乎不起作用。我的错在哪里?在
代码如下:
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)
你可能想试试我的代码:
这是我基于CLRs-KMP算法编写的一个类,其中包含了您所追求的内容。注意这里只接受DNA“字符”。在
试试这个:
相关问题 更多 >
编程相关推荐