w****3 发帖数: 110 | 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]]相等的吗? |