问一个KMP算法的问题# JobHunting - 待字闺中
w*3
1 楼
新手，看了一整天KMP算法，还是没有搞得很清楚。希望大牛给讲讲。
假设一个pattern string p， KMP的第一步是用pattern生成一个next array。根据这
个博客里讲的
http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.h
根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
1)若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1;
2)若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移
动，显然k=next[k]。
void getNext(char *p,int *next)
{
int j,k;
next[0]=-1;
j=0;
k=-1;
while(j
if(k==-1||p[j]==p[k]) //匹配的情况下,p[j]==p[k]
{
j++;
k++;
next[j]=k;
}
else //p[j]!=p[k]
k=next[k];
}
}
我的问题是为什么最后一个statement是k = next[k]而不是直接check k = 0是否匹配
呢？我想了半天想不出来反例。不应该是P[k]总是和p[next[k]]相等的吗？
假设一个pattern string p， KMP的第一步是用pattern生成一个next array。根据这
个博客里讲的
http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.h
根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
1)若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1;
2)若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移
动，显然k=next[k]。
void getNext(char *p,int *next)
{
int j,k;
next[0]=-1;
j=0;
k=-1;
while(j
if(k==-1||p[j]==p[k]) //匹配的情况下,p[j]==p[k]
{
j++;
k++;
next[j]=k;
}
else //p[j]!=p[k]
k=next[k];
}
}
我的问题是为什么最后一个statement是k = next[k]而不是直接check k = 0是否匹配
呢？我想了半天想不出来反例。不应该是P[k]总是和p[next[k]]相等的吗？