エイホ–コラシック法 - Wikipedia

エイホ–コラシック法（英: Aho–Corasick algorithm）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである[1]。 概要[編集] エイホ–コラシック法は、入力テキストについて有限の文字列群（辞書）の各要素を探す辞書式マッチングアルゴリズムの一種である。全パターンのマッチングを一斉に探索するため、そのアルゴリズムの計算量はパターン群の長さに対しても対象テキストの長さに対しても線形であり、さらに見つかったマッチングの数に対しても線形である。全てのマッチングを検出するため、パターン群にサブ文字列があれば、重複して検出される点に注意されたい（つまり、辞書が a, aa, aaa, aaaa で、入力テキストが aaaa の場合など）。 大まかに言えば、このアルゴリズムはトライ木を構築し、サフィックス木的に文字

[Sampo]

Aho-Corasick法。ウィルススキャンのようにテキストから複数のパターンを1パスで探索するアルゴリズム。

[mooz]

文字列を一度スキャンするだけで, 辞書中にある全ての単語を抜き出せる.

[hitsujibane]

文字列探索アルゴリズム