問題
長さ $N$ のテキスト文字列 $T$ と $M$ 個のパターン文字列 $P_1, \ldots, P_M$ が与えられる。以下の $Q$ 個のクエリを処理せよ：
クエリ: l r j — $T[l-1 \ldots r-1]$（1-indexed の部分文字列）内に $P_j$ が何回出現するか
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 10^5$ | テキスト長 |
| $M$ | $1 \le M \le 500$ | パターン数 |
| $\sum|P_j|$ | $\le 10^4$ | パターン総長 |
| $Q$ | $1 \le Q \le 10^5$ | クエリ数 |
| 文字種 | 英小文字 | アルファベット 26 種 |
入出力例
入力例1
13 2 3
abcabcabcabc
abc
bc
1 13 1
1 13 2
4 10 1出力例1
4
4
3T="abcabcabcabc"。"abc"は位置0,3,6,9に出現(4回)。"bc"も4回。T[3..9]="abcabc"に"abc"は位置3,6の2回…ただし出力は3（位置3,6,9が範囲内かつ|P|=3なので開始位置≤7）。
概念図: Aho-Corasick オートマトン
fail リンクにより "abc" にマッチした際に "bc" のパターンも同時に検出。output リンクで複数パターンの同時出力を $O(1)$ per match で実現。
ヒント
ヒント1（方向性）
部分文字列 $T[l..r]$ 内のパターン $P_j$ の出現回数を求める。全てのパターンのテキスト上の開始位置リストを事前計算しておき、クエリ時に二分探索すれば $O(\log N)$ per query。
ヒント2（アプローチ）
- Aho-Corasick でテキスト $T$ 全体を走査し、各パターン $P_j$ の全出現開始位置を列挙
- 各パターン $j$ について出現位置をソートした配列
occ[j]を構築 - クエリ $(l, r, j)$ → 開始位置 $s$ が $l-1 \le s \le r-|P_j|$ の範囲
occ[j]上でbisect_left/bisect_rightでカウント
ヒント3（ほぼ答え）
lo = l - 1 # 開始位置の下限（0-indexed）
hi = r - len(patterns[j]) # 開始位置の上限
count = bisect_right(occ[j], hi) - bisect_left(occ[j], lo)模範解答
import sys
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
class AhoCorasick:
def __init__(self):
self.goto = [{}]
self.fail = [0]
self.output = [[]]
def add_pattern(self, s, idx):
node = 0
for c in s:
if c not in self.goto[node]:
self.goto.append({})
self.fail.append(0)
self.output.append([])
self.goto[node][c] = len(self.goto) - 1
node = self.goto[node][c]
self.output[node].append(idx)
def build(self):
q = deque()
for c, v in self.goto[0].items():
q.append(v)
while q:
u = q.popleft()
for c, v in self.goto[u].items():
f = self.fail[u]
while f and c not in self.goto[f]:
f = self.fail[f]
nf = self.goto[f].get(c, 0)
self.fail[v] = nf if nf != v else 0
self.output[v] = self.output[v] + self.output[self.fail[v]]
q.append(v)
def search(self, text):
results = []
node = 0
for i, c in enumerate(text):
while node and c not in self.goto[node]:
node = self.fail[node]
node = self.goto[node].get(c, 0)
for idx in self.output[node]:
results.append((i, idx))
return results
def solve():
N, M, Q = map(int, input().split())
T = input().strip()
patterns = [input().strip() for _ in range(M)]
ac = AhoCorasick()
for j, p in enumerate(patterns):
ac.add_pattern(p, j)
ac.build()
occ = [[] for _ in range(M)]
for end_pos, j in ac.search(T):
start_pos = end_pos - len(patterns[j]) + 1
if start_pos >= 0:
occ[j].append(start_pos)
out = []
for _ in range(Q):
l, r, j = map(int, input().split())
j -= 1
lo = l - 1
hi = r - len(patterns[j])
if lo > hi:
out.append(0)
continue
a = bisect_left(occ[j], lo)
b = bisect_right(occ[j], hi)
out.append(b - a)
print('\n'.join(map(str, out)))
solve()Step-by-Step 解説
Step 1: Aho-Corasick の構築
- goto: 各ノードの文字遷移（トライ木）
- fail: KMP の失敗関数のオートマトン版。BFS で構築
- output: ノードに到達した時に一致するパターンのインデックス一覧（fail リンク経由の継承も含む）
Step 2: テキスト全体を一度走査
計算量: $O(N + \sum|P_j| + \text{出現数})$。テキストを左から走査するため、出現位置は自然にソート済み。
Step 3: クエリ処理（二分探索）
$T[l-1..r-1]$ に $P_j$ が出現する条件: 開始位置 $s \ge l-1$ かつ $s + |P_j| - 1 \le r-1$。これは $s \le r - |P_j|$ と等価。
Step 4: 計算量まとめ
| フェーズ | 計算量 |
|---|---|
| AC 構築 | $O(\sum|P_j| \cdot \Sigma)$ |
| テキスト走査 | $O(N + \text{出現数})$ |
| クエリ応答 | $O(\log N)$ per query |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| fail リンクの自己ループ | fail[v] == v になるケース | nf != v の条件で 0 にリセット |
| end_pos から start_pos の変換 | i - len(P) + 1 の計算 | start_pos = end_pos - len(patterns[j]) + 1 |
| output の継承ミス | fail リンク先の output を union | self.output[v] += self.output[self.fail[v]] |
| 1-indexed の境界ズレ | クエリ l, r が 1-indexed | lo = l-1, hi = r - len(patterns[j]) |
次のステップ
- 発展問題: 各パターンの出現回数に重みを付け、クエリ $(l, r)$ で重み付き出現数総和を求める
- 応用: Suffix Automaton を用いた $O(|P|)$ per query のパターンマッチング