Day 113-Q3 — Aho-Corasick fail木上のオフライン集約クエリ（Euler Tour + BIT）

2026-08-05 赤色 Master / Phase 8+ ★★★★★★★★★ 複数パターン出現回数の一括集計

問題

小文字英字からなる $K$ 個のパターン文字列 $P_1,\dots,P_K$ と、小文字英字からなる文字列 $T$ が与えられる。それぞれのパターン $P_i$ が $T$ の中に（重なりを許して）何回出現するかを求めよ。

入力形式

K
P_1
P_2
...
P_K
T

制約

$1 \le K \le 10^5$
$\sum |P_i| \le 2\times10^5$
$1 \le |T| \le 2\times10^5$
全て小文字英字のみ

入出力例

入力例1

3
ab
b
bc
ababc

出力例1

2
2
1

T=ababc で ab は位置0-1,2-3の2回、b は位置1,3の2回、bc は位置3-4の1回出現。

入力例2

2
a
aa
aaa

出力例2

3
2

概念図: fail木の部分木和 = パターンの出現回数

fail木上で「b」の部分木には「ab」「bc」などの長い一致が含まれる root "b" "a" "ab" "bc" fail("ab") = "b"（"b"は"ab"の最長真の接尾辞） fail("bc") = "b"（同様） Tを1回なぞりcnt[到達ノード]+=1 → fail木の部分木和で各パターンの出現回数を一括取得

ヒント（段階的開示）

ヒント1: 方向性
パターンごとに $T$ を愚直に走査すると $O(K\cdot|T|)$ で間に合わない。Aho-Corasickオートマトンで $T$ を1回だけなぞって全パターンの出現を同時に検出したいが、各文字位置で一致したパターンを全部数え上げると最悪 $O(|T|^2)$ になりうる。
ヒント2: アプローチ
Aho-Corasickの各ノードはfailリンク（最長の真の接尾辞ノードへのリンク）を持つ。failリンクを親として見たfail木では「あるノードの文字列は子孫ノードの文字列の接尾辞」という関係が成り立つ。$T$をなぞって到達ノードに$+1$しておき、fail木上で部分木和を取れば各パターンの出現回数が一括で求まる。部分木和はオイラーツアー$[tin,tout]$ + BITで実現する。
ヒント3: 誘導（コード骨格） 
cur = 0
for ch in T:
    cur = goto[cur][ch]
    bit_add(tin[cur], 1)
# 各パターンiの終端ノードv:
# 出現回数 = bit_range_sum(tin[v], tout[v])

模範解答 (Python)

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    K = int(data[idx]); idx += 1
    patterns = []
    for _ in range(K):
        patterns.append(data[idx].decode()); idx += 1
    T = data[idx].decode(); idx += 1

    ALPHA = 26
    goto = [[-1] * ALPHA]
    fail = [0]
    end_node = [0] * K

    def new_node():
        goto.append([-1] * ALPHA)
        fail.append(0)
        return len(goto) - 1

    for i, p in enumerate(patterns):
        cur = 0
        for ch in p:
            c = ord(ch) - 97
            if goto[cur][c] == -1:
                goto[cur][c] = new_node()
            cur = goto[cur][c]
        end_node[i] = cur

    n_nodes = len(goto)
    q = deque()
    for c in range(ALPHA):
        if goto[0][c] == -1:
            goto[0][c] = 0
        else:
            fail[goto[0][c]] = 0
            q.append(goto[0][c])
    while q:
        u = q.popleft()
        for c in range(ALPHA):
            v = goto[u][c]
            if v == -1:
                goto[u][c] = goto[fail[u]][c]
            else:
                fail[v] = goto[fail[u]][c]
                q.append(v)

    children = [[] for _ in range(n_nodes)]
    for v in range(1, n_nodes):
        children[fail[v]].append(v)

    tin = [0] * n_nodes
    tout = [0] * n_nodes
    timer = 0
    stack = [(0, False)]
    while stack:
        u, processed = stack.pop()
        if processed:
            tout[u] = timer - 1
        else:
            tin[u] = timer
            timer += 1
            stack.append((u, True))
            for v in children[u]:
                stack.append((v, False))

    bit = [0] * (n_nodes + 1)

    def bit_add(i, val):
        i += 1
        while i <= n_nodes:
            bit[i] += val
            i += i & (-i)

    def bit_sum(i):
        i += 1
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s

    def range_sum(l, r):
        if r < l:
            return 0
        return bit_sum(r) - bit_sum(l - 1)

    cur = 0
    for ch in T:
        c = ord(ch) - 97
        cur = goto[cur][c]
        bit_add(tin[cur], 1)

    out = []
    for i in range(K):
        v = end_node[i]
        out.append(str(range_sum(tin[v], tout[v])))
    print("\n".join(out))

main()
計算量: 構築 $O(\sum|P_i|\cdot26)$、$T$走査 $O(|T|\log N)$、各クエリ$O(\log N)$。アルファベット{a,b}・パターン長1〜3・T長1〜15のランダム200件で愚直な部分文字列カウントと全出力一致を確認済み。

Step-by-Step 解説

1トライ木の構築
各パターンを1文字ずつ辿り、終端ノード番号をend_node[i]に記録する。
2goto関数とfailリンクをBFSで構築する
トライ上に遷移がなければfail[u]の同じ文字への遷移を使う（完全なgoto関数を作る）。
3fail木を構築しオイラーツアーで区間化する
反復DFSで各ノードの担当区間 $[tin,tout]$ を求める。
4Tを1回なぞりながらBITに加算する
現在のオートマトン状態を1文字ずつ更新し、その位置でbit_add(tin[cur],1)する。
5部分木和クエリで出現回数を求める
range_sum(tin[v],tout[v])がパターンPiの出現回数と一致する。

よくあるミス

ミス原因正しい書き方
ノードごとに一致パターンを都度全列挙する最悪O(|T|^2)になる印を1つ置いて後でまとめて部分木和を取るオフライン処理にする
fail木でのオイラーツアーを再帰で書く1文字ずつの鎖状トライで再帰深さがO(Σ|Pi|)に達しうる反復スタックでDFSを行う
toutを最後に訪問した子のtoutで求めようとする兄弟の処理順で区間が不連続になりうるprocessedフラグ付きスタックでtimer-1をtoutとする
同一文字列パターンを別ノード扱いしてしまうトライ構築で新規ノードを作ると出現回数の対応が崩れる同じ文字列は必ず同じノードに帰着させる

次のステップ

  • 発展: 「Tの中で最も出現回数が多いパターン」をオンラインで求めるクエリに拡張する
  • 発展: fail木の重心分解（Day017 Q2, Day033 Q5）でパターン集合が動的に追加される設定に拡張する
  • 発展: Suffix Automaton（Day086 Q1）を使った類題との解法アプローチを比較する

自己評価

自分の回答

気づき・メモ