エイホ–コラシック法
エイホ–コラシック法は、入力テキストについて有限の文字列群(辞書)の各要素を探す辞書式マッチングアルゴリズムの一種である。全パターンのマッチングを一斉に探索するため、そのアルゴリズムの計算量はパターン群の長さに対しても対象テキストの長さに対しても線形であり、さらに見つかったマッチングの数に対しても線形である。全てのマッチングを検出するため、パターン群にサブ文字列があれば、重複して検出される点に注意されたい(つまり、辞書が a, aa, aaa, aaaa で、入力テキストが aaaa の場合など)。
大まかに言えば、このアルゴリズムはトライ木を構築し、サフィックス木的に文字列(例えばabc)を表すノードからその最長サフィックス(接尾部、例えばbc)を表すノードがあればそれへリンクし、さもなくば c を表すノードがあればそれへリンクし、それもなければルートノードにリンクする。このような最長サフィックスへのリンクを全てのノードが持っているため、そのリンクリストを辿ることで全てのマッチングを列挙できる。実行時にはトライ木として働き、最長のマッチングを探すと共に、サフィックスのリンクリストを活用することで計算量を線形に抑えている。辞書にあるノードに到達すると、その単語とそこからリンクされている辞書に含まれるノードが、マッチングした位置と共に出力される。
(例えばコンピュータウイルスのデータベースのように)パターン辞書が更新されると、オフラインでオートマトンの構築がなされ、それを今後使用するよう格納する。この場合、実行時の計算量は入力の長さとマッチすべきエントリ数に対して線形である。
UNIXのコマンド fgrep は本来エイホ-コラシック法に基づいていた。