DMP構築の過程をKMPアルゴリズムで理解する方法

Question

私は、書籍アルゴリズム4thのKMPアルゴリズムを学んでいます。私はアルゴリズムの大部分を理解することができましたが、数日の間、dfa構築のプロセスで立ち往生しています。

例えば、ABABACのパターンをとってください。 Cに不一致がある場合（dfaの状態が5）、テキスト内の文字を右にシフトする必要があります。したがって、私たちが知っているパターン文字はBABAです。しかし、どのように建設中のDFAの次の状態を把握するには？我々はフルバックアップが私たちを残してしまうことを学ぶためにDFAを使用して、我々はJ = 5で一致していたときにDFAがABABACのために、何をすべきかを決定するために、例えば

：私は、下のテキストを理解することができませんでした状態3ではBABAですので、dfa[][3]をdfa[][5]にコピーできます。

「フルバックアップはBABAの状態3になります」とは何ですか、指定された入力がないときにこの結論を得る方法は何ですか？そして、私はテキストに残っているグラフを理解できません。誰でもその意味を説明できますか？私は2、3日間自分でそれを理解しようとしましたが、まだそれを得ることができませんでした。ありがとうございました！あなたが入力文字列に一致しているとき

And you can read the segment of Algorithms 4th here.

Answer 1

、あなただけのパターンの最初の5つの文字にマッチした後の状態5に入ると、パターンの最初の5つの文字をすることができますABABA 。したがって、どの入力文字列を使用しても、はを知っています。状態5より前のテキストは「ABABA」です。

状態5で不一致が発生した場合、はに4文字をバックアップして再度一致を試みることができます。しかし、状態5の前にどのようなテキストを表示しなければならないかを知っているので、実際に何が起こるか把握するために入力テキストは実際には必要ありません。同じ場所に戻ったときにどのような状態になるのかを事前に把握することができます。

バックアップ4つの文字と状態0へ行く：

0：BABA

A一致していない、事前ように状態0

0に行く：ABA

Aが一致しましたしたがって、状態1に進む

1：BA

Bが一致し、状態2

2に行く：

Aマッチし、状態3

3に進みます。

今、我々は前の状態5を見た入力に戻って場所にしています、今は状態3に入っています。

これは、状態5で不一致が発生した場合に常に発生します。実際にこれを実行するのではなく、「状態5で不一致が発生した場合は状態3に進みます」というメモを作成します。

ほとんどのKMP実装では実際にはfailure_table[5]=3の障害テーブルが作成されることに注意してください。あなたの実装例では、代わりに完全なDFA[char][state]が構築されているので、障害ケースについては、状態3から状態5へのすべての遷移をコピーします。つまり、「状態5で不一致が発生した場合は、状態3で何をしても構いません」と言います。

は、私たちが状態5での不整合を取得すると、私たちはDFAを使用することができます私たちは持っている...今度は、これらの障害状態の計算をスピードアップさせ

に移動する前にABOVE

をすべてを理解しますDFAを「BABA」に適用することで、次の一致可能な時点から入力をバックアップして再スキャンした場合に何が起きるかを理解するために、状態3になるので、状態3を状態5の「失敗状態」としましょう。

ステート5の障害状態を計算するには4パターンのチャクラを処理する必要がありますが、は、その作業の状態4の障害状態を計算したときにDFAを「BAB」に適用して状態2で終了しました。

状態5の障害状態を把握するには、状態4（状態2）の障害状態、パターン内の次の文字（入力の状態4の後に来る「A」）を処理します。