これはどのパターンマッチングアルゴリズムですか？

Question

私はTheory & Struc（Seymour Lipschuz）の問題を読んでいました。

私が読んでいたセクションの画像を提供しましょう。 。

このセクションでは、「第2のPatter-Matching Algorithm」という名前のパターンマッチングアルゴリズムについて説明します。

これはどのアルゴリズムですか？これはBoyer-MooreかKMPかHorspoolか何ですか？

または、これは作成者が作成した新しいアルゴリズムですか？

Answer 1

私はこれがKMPアルゴリズムであると信じています。 KMPは、「特定の文字に不一致がある場合、パターン文字列のどれくらいがまだ一致していますか？」というオートマトンである「障害テーブル」を作成します。パターンの前処理も行いますが、一致する文字列は処理しません。さらに、KMPの一般化であるAho-Corasickアルゴリズムを見ると、一度に複数のパターンで動作するこのオートマトンのより一般的なバージョンを構築します。その結果、私はあなたがKMPを見ていると確信しています。