kmpアルゴリズムの理解
1963 ワード
//*********************の著者:cncoderalexブログ:http://blog.csdn.net/cncoderalex ***************************************************
下の二つのコードは構造の法アルゴリズムの道博主jurly大神のブログから抜粋します。ここで、私はコードだけをマークして注釈します。自分の学習の心得と言えます。
下の二つのコードは構造の法アルゴリズムの道博主jurly大神のブログから抜粋します。ここで、私はコードだけをマークして注釈します。自分の学習の心得と言えます。
// next
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k] ,p[j]
if (k == -1 || p[j] == p[k])
{
++j;
++k;
// next , 4
if (p[j] != p[k])
next[j] = k; //
else
// p[j] = p[ next[j ]], ,k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
next配列を求めて、最初はnext[0]=-1で、これは固定されています。kは現在最新に求められている最長の共通文字列の前の拡張長さです。jは0から始まり、現在の文字p[j]とp[k]が等しいか否かによって、実際に求められるのはnext[j+1]の値であるため、サイクルはpLen-1より小さくても良い。p[i]==p[k],next[i+1]=next[i]+1=k+1、そうでなければnextはまっすぐに遡ります。つまり、k=next[k]は、0番目の文字、つまりk=-1までです。また、ここでnext配列に最適化があります。つまりp[j]!p[k]でないとnext[j]も前にさかのぼります。jurly大神はずっと遡ると言いますが、コード実行から見れば、一歩だけ遡って、k値のように遡りません。ここで、私は自分の理解で補足します。なぜならば、転送によってp[next[k]を確保します。p[k],p[k]==p[j]ですから、p[j]があります。p[next[k]ですint KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//① j = -1, ( S[i] == P[j]), i++,j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//② j != -1, ( S[i] != P[j]), i ,j = next[j]
//next[j] j next
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}