文字列照合アルゴリズム

KMP法

クヌース-モリス-プラット(Knuth-MorrisPratt)法

テキストSの中に文字列Wがあるかを調 べる

あらかじめ文字列Wに対するパターン照合テー ブルを作る

パターン照合テーブル

テキストS中の文字とW中の文字の照合に失敗したときに、W中の参照位置をいくつ戻せばよいのかを格納したテーブル(配列)