古典文字列アルゴリズム Aho–Corasick を Go の CLI として書いた。辞書全体（多数パターン）を、パターン数に依らず
O(text + patterns + matches)の 1 パスで同時マッチする構造。実装の肝は 3 層: (1) 全パターンの trie（goto）、(2) failure link — 次の文字でマッチが伸びないとき、いま一致している文字列の「最長の真の接尾辞であって、かつどれかのパターンの接頭辞」へ飛ぶ。これは KMP の失敗関数を 1 パターンから集合へ一般化したもの、(3) dictionary-suffix link — 1 箇所で同時に終わる複数パターン（"hers" は "he" も終える）を全部報告する。確率的データ構造シリーズ（#274-278）から古典アルゴリズムへ路線変更。
📦 GitHub: https://github.com/sen-ltd/aho-corasick-cli
問題設定
探したい針（パターン）が 1 本ではなく多数ある。単一パターン検索（KMP のような良いものでも）をパターンごとに回すと O(P · text)（P はパターン数）。Aho–Corasick は 1 パスで済ませる: 辞書全体からオートマトンを組み、テキストを 1 回走査して、重複を含む全マッチを吐く。
CLI はこう動く（実出力）:
$ ac search -p he -p she -p his -p hers ushers
1 she
2 he
2 hers # 重複マッチも 1 パスで全部見つかる
— 3 match(es) of 4 pattern(s) in 6 bytes, automaton has 10 states
$ ac count --patterns signatures.txt --from app.log
ERROR 6034
WARN 4107
timeout 2025
connection refused 1960
...
— 22323 total match(es) in one pass over 542889 bytes
「ログ 1 本を舐めて、複数のエラーシグネチャの出現数を一括カウント」——まさに Aho–Corasick の出番。
構築: trie ＋ 2 種類のリンク
1. trie（goto）。全パターンを挿入。辿るとテキストの一致接頭辞を消費する。
2. failure link。次の文字でマッチが伸びないとき、テキストを読み直さずにどこへ行くか? いま一致している文字列の 最長の真の接尾辞であって、かつどれかのパターンの接頭辞 へ。これはまさに KMP の失敗関数を、1 パターンから集合へ一般化したもの。BFS で、各ノードのリンクを親から導いて構築する:
f := m.fail[u]
for {
if c, ok := m.children[f][b]; ok { m.fail[v] = c; break }
if f == 0 { m.fail[v] = 0; break }
f = m.fail[f]
}
failure link は必ず より浅い ノードを指すので、走査がテキスト上を後戻りしない。これが線形性の肝。
3. dictionary-suffix link。1 つのテキスト位置で複数パターンが同時に終わることがある——hers を一致させると he や her も終わる。各ノードを「同じ位置で終わる、より短いパターン」へリンクし、報告時にその鎖を辿って全部吐く:
if m.out[m.fail[u]] != -1 { m.dict[u] = m.fail[u] } else { m.dict[u] = m.dict[m.fail[u]] }
TestDictSuffixReportsNested は "hers" のマッチで hers・he・her が報告されることを、TestClassicUshers は教科書の {he, she, his, hers} × "ushers" を pin する。
走査: 1 回の線形パス
node := 0
for i := 0; i < len(text); i++ {
node = m.step(node, text[i]) // goto、失敗時は failure link を辿る
for t := node; t != -1; t = m.dict[t] // dictionary-suffix の鎖を辿る
if pid := m.out[t]; pid != -1 { emit(pid, endsAt: i) }
}
step は goto 辺が見つかる（か root に着く）まで failure link を辿る。ならして全体はテキスト長に線形。TestAgainstBruteForce が、重複ありの混合パターンで素朴な O(P·n) マッチャとカウント一致を確認する。
UTF-8
マッチはバイト単位なので、マルチバイトのパターンもそのまま動き、オフセットはバイトオフセットになる。TestUnicodeByteMatching は 東京都 を重複パターン 東京・京都・東京都 で検索し、3 つとも見つける。
aho/aho.go — オートマトン: trie, failure & dict link, FindAll / Count（テスト 10 件）
main.go — CLI: search / count, パターンは flag or ファイル, テキストは arg/ファイル/stdin
まとめ
Aho–Corasick は「多数の針を 1 パスで」の定番。鍵は failure link が KMP の一般化であること、dictionary-suffix link で重複マッチを取りこぼさないこと、そして全体が テキスト長に線形であること。#274-278 の確率的データ構造から古典文字列アルゴリズムへ振ったが、「前処理でオートマトンを組み、本番は 1 パスで安く」という発想は同じ系譜だ。