Day 153-Q5 — Aho-Corasickオートマトン（複数パターン同時マッチング）

2026-09-14 赤色 Master / Phase 8+ ★★★★★★★★★ トライ+fail link構築でテキスト1回走査からO(|T|+ΣP+Z)で全出現を集計

問題

$M$ 個のパターン文字列 $P_1,\dots,P_M$（小文字英字のみ）とテキスト $T$（小文字英字のみ）が与えられる。$T$ の中に現れる $P_1,\dots,P_M$ の出現回数の総和（同じパターンが複数回・重複して現れる場合も全てカウント）を求めよ。

入力形式

M
P_1
P_2
:
P_M
T

制約

$1 \le M \le 100$
$1 \le |P_i| \le 100$
$1 \le |T| \le 10^5$

入出力例

入力例1

4
he
she
his
hers
ahishers

出力例1

4

概念図：トライ木とfail link

パターン {he, she, his, hers} のトライ木 root h s e* i h r s* e* s* fail: s→h *=パターン終端ノード（cnt>0）。fail linkはBFS順に構築、cntはfail経由で伝播

ヒント（段階的開示）

ヒント1（方向性）

パターンを1つずつ愚直に`T.count(P_i)`していくと、パターン数$M$とテキスト長$|T|$の積で計算量が膨らむ。全パターンを1つの自動機にまとめてテキストを1回だけ走査する発想に切り替える必要がある。

ヒント2（アプローチ）

全パターンを1本のトライ木にまとめ、KMP法の失敗関数を木全体に一般化したfail linkを根からのBFSで構築する。あるノードのfail linkは「親のfail linkを辿った先で同じ文字の子を持つノード」として求まる。各ノードの「そのノードで終わるパターン数」をfail link経由で合算しておく。

ヒント3（誘導） 
def build(self):
    q = deque()
    for c, nxt in self.children[0].items():
        self.fail[nxt] = 0
        q.append(nxt)
    while q:
        u = q.popleft()
        self.cnt[u] += self.cnt[self.fail[u]]
        for c, v in self.children[u].items():
            f = self.fail[u]
            while f and c not in self.children[f]:
                f = self.fail[f]
            self.fail[v] = self.children[f].get(c, 0)
            q.append(v)

模範解答 (Python)

import sys
from collections import deque


class AhoCorasick:
    def __init__(self):
        self.children = [{}]
        self.fail = [0]
        self.cnt = [0]

    def add(self, s):
        node = 0
        for c in s:
            if c not in self.children[node]:
                self.children[node][c] = len(self.children)
                self.children.append({})
                self.fail.append(0)
                self.cnt.append(0)
            node = self.children[node][c]
        self.cnt[node] += 1

    def build(self):
        q = deque()
        for c, nxt in list(self.children[0].items()):
            self.fail[nxt] = 0
            q.append(nxt)
        while q:
            u = q.popleft()
            self.cnt[u] += self.cnt[self.fail[u]]
            for c, v in list(self.children[u].items()):
                f = self.fail[u]
                while f and c not in self.children[f]:
                    f = self.fail[f]
                self.fail[v] = self.children[f][c] if c in self.children[f] else 0
                q.append(v)

    def count_matches(self, text):
        node = 0
        total = 0
        for c in text:
            while node and c not in self.children[node]:
                node = self.fail[node]
            node = self.children[node].get(c, 0)
            total += self.cnt[node]
        return total


def main():
    data = sys.stdin.read().split()
    idx = 0
    m = int(data[idx]); idx += 1
    ac = AhoCorasick()
    for _ in range(m):
        ac.add(data[idx]); idx += 1
    text = data[idx]

    ac.build()
    print(ac.count_matches(text))


main()

Step-by-Step 解説

1トライ木の構築
`he,she,his,hers`を1本のトライにまとめる。`h`から始まる枝は`he`と`his`で共有される。
2fail linkをBFSで構築
深さ1のノード(`h`,`s`)のfail linkは根。深さ2以降は「親のfail linkを辿って同じ文字の子」を探す。
3cntの伝播
fail木の祖先にend-of-patternがあれば`cnt`が合算される。
4テキスト"ahishers"を1回走査
位置1-3で`his`、3-5で`she`、4-5で`he`、4-7で`hers`がマッチし合計4件。出力例1の`4`と一致。

よくあるミス

ミス原因正しい書き方
fail linkをDFSで構築しようとするKMP法の直感を引きずるfail linkは必ずBFS順（浅い深さから）で構築
cntのfail経由合算をBFSより前に行う処理順序の誤りuがキューから出た時点で加算する
テキスト走査でfail link辿りを書き忘れる単純なトライ探索のまま実装マッチしない文字が来たら`node=fail[node]`を辿る
出現位置ではなく種類数を数える「総和(重複カウント)」の意味の読み違え`cnt`は延べ出現数を加算し続ける
パターン外の文字の遷移を考慮しない一般化する際の見落とし`children[node].get(c,0)`で安全な遷移にする

次のステップ

  • 発展: 出現位置ごとにどのパターンが何個マッチしたかを全て列挙し、$Z$（総出現数）に比例した追加コストで済むことを確認する。
  • 次回予告: フェーズ8+ ローテーション継続（新規テーマ選定）

自己評価

自分の回答

気づき・メモ