Knuth-Morris-Pratt アルゴリズムに関するウィキペディアの記事を読んでいますが、ジャンプ/部分一致テーブルで値がどのように見つかるかについて混乱しています。
i | 0 1 2 3 4 5 6
W[i] | A B C D A B D
T[i] | -1 0 0 0 0 1 2
誰かがショートカットルールをより明確に説明できる場合、文は
「適切なプレフィックスであり、長さ 2 (可能な最大) の W[2] で終わる適切なサフィックスを発見したとしましょう」
紛らわしいです。適切なサフィックスが W[2] で終わる場合、サイズは 3 ではないでしょうか?
また、サイズ 1 のプレフィックスとサフィックスがあるのに、なぜ T[4] が 1 でないのか疑問に思っています: The A.
提供できるヘルプをありがとう。
失敗関数 T[i] は i をインデックスとしてではなく、長さとして使用することに注意してください。したがって、T[2] は、文字で終わる文字列によって形成される最長の適切な境界ではなく、W の最初の 2 文字から形成される文字列の最長の適切な境界 (プレフィックスとサフィックスの両方である文字列) の長さを表します。 2. これが、T[2] の可能な最大値が 3 ではなく 2 である理由です。W の最初の 2 文字から形成される部分文字列の長さは 2 を超えることはできません。
この解釈を使用すると、T[4] が 1 ではなく 0 である理由も簡単にわかります。W の最初の 4 文字から形成される W の部分文字列は ABCD であり、適切な接尾辞でもある適切な接頭辞はありません。
お役に立てれば！
「適切なプレフィックスであり、長さ 2 (可能な最大) の W[2] で終わる適切なサフィックスを発見したとしましょう」
わかりました、長さは最大 2 にすることができます。それは正しいです。これが理由です...
W[0]=AW[1]=AW[2]=A 、つまりパターンが「AAA」であるため、(最大長の)適切な接頭辞は「AA」(左から右)であり、(最大長) 適切なサフィックスは "AA" (右から左) にすることができます //はい、プレフィックスとサフィックスには重複があります (中央の "A")
したがって、値は 3 ではなく 2 になり、プレフィックスが適切でない場合にのみ 3 になります。