私はこれに関するほとんどの文献を読んで最善を尽くしましたが、KMP アルゴリズムで使用される失敗関数がどのように構築されるかについてはまだ何も理解していません。私は主にhttp://community.topcoder.com/tc?module=Static&d1=tutorials&d2=string検索チュートリアルを参照してきましたが、これはほとんどの人が優れていると考えています。しかし、私はまだそれを理解していません。お手数をおかけしますが、もう少し分かりやすくご説明いただけますと幸いです。
質問する
9051 次
2 に答える
9
失敗関数は実際にこれを教えてくれます。文字列のX文字に一致した場合、検索文字列のプレフィックスでもあるように、そのような文字列の最長のサフィックスは何ですか。
あなたはそれがどのように構築されているかを尋ねています、アプローチは非常に簡単です。
文字列の最後に新しい文字を追加する場合、つまりf [x]を作成している場合、それが位置f [x-1]の文字と一致する場合、f[x]は単純にf[x-1]になります。 ]+1。
一致しない他のケースでは、ますます小さいサフィックスを見つけて、それらが一致するかどうかを確認しようとします。
たとえば"accadaccac"、失敗関数を作成している単語があり、文字を追加したとします'c'。最後の文字である文字の失敗関数を作成しているとしましょう'c'。
- 最初に前の文字の失敗関数を確認します。接尾辞
"acca"を接頭辞と一致させることができるため、失敗関数は4でした。"acca"次に、文字を追加すると、後続'c'の文字の接頭辞と一致しません。'd'"acca" - したがって、最後の適切な接尾辞に戻ります。
"acca"の接頭辞でもあるが"accadaccac"、「acca」よりも小さい接尾辞を検索しています。その質問に対する答えは、f [length（ "acca"）-1]、またはf [3]、つまりf [3] = 1です。これは、長さ1の接尾辞（文字のみ'a'）も検索のプレフィックスであるためです。ストリング。 - これで、位置1の文字と一致するかどうかを試すことができ
'c'、出来上がり、一致するので、f [9] = f [f [8] -1] +1=2であることがわかります。
これがお役に立てば幸いです。幸運を！:)
于 2012-07-01T13:14:48.220 に答える
-1
http://www.oneous.com/Tutorial-Content.php?id=24
この Web サイトの学習リソースを使用して、KMP アルゴリズムと失敗関数を理解できます。また、コードを取得して、例の文字列を手動で実行してみてください。ただし、その動作を理解する最善の方法は、基本アルゴリズムのいくつかのバリエーションで自分でコーディングすることです。SPOJ の NHAY と PERIOD から始めることをお勧めします。
于 2012-07-03T09:59:37.050 に答える