Day 030-Q1 — Aho-Corasick法（複数パターン文字列マッチング）

問題

$N$ 個のパターン文字列と $Q$ 個のテキストに対し、各テキスト中のパターン種類数と延べ出現回数を求めよ。

制約

入出力例

3 2
ab
bc
abc
abcbc
xyzab

3 4
1 1

abcbc: ab(1), bc(2), abc(1) → 種類3, 延べ4。xyzab: ab(1) のみ。

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from collections import deque
input = sys.stdin.readline

class AhoCorasick:
    def __init__(self):
        self.goto = [{}]
        self.fail = [0]
        self.output = [[]]
    def add_pattern(self, pattern, idx):
        state = 0
        for c in pattern:
            if c not in self.goto[state]:
                self.goto[state][c] = len(self.goto)
                self.goto.append({})
                self.fail.append(0)
                self.output.append([])
            state = self.goto[state][c]
        self.output[state].append(idx)
    def build(self):
        q = deque()
        for c, s in self.goto[0].items():
            q.append(s)
        while q:
            r = q.popleft()
            for c, s in self.goto[r].items():
                q.append(s)
                state = self.fail[r]
                while state != 0 and c not in self.goto[state]:
                    state = self.fail[state]
                f = self.goto[state].get(c, 0)
                if f == s:
                    f = 0
                self.fail[s] = f
                self.output[s] = list(set(self.output[s]) | set(self.output[f]))
    def search(self, text):
        state = 0
        results = []
        for c in text:
            while state != 0 and c not in self.goto[state]:
                state = self.fail[state]
            state = self.goto[state].get(c, 0)
            for pat_idx in self.output[state]:
                results.append(pat_idx)
        return results

def main():
    N, Q = map(int, input().split())
    patterns = [input().strip() for _ in range(N)]
    texts = [input().strip() for _ in range(Q)]
    ac = AhoCorasick()
    for i, p in enumerate(patterns):
        ac.add_pattern(p, i)
    ac.build()
    for text in texts:
        hits = ac.search(text)
        kinds = len(set(hits))
        total = len(hits)
        print(kinds, total)

main()

Step-by-Step 解説

よくあるミス

次のステップ

• 出現位置の列挙
• 動的追加・削除（Incremental AC）

自己評価

自分の回答

気づき・メモ