Day 012-Q5 — 高度文字列（Suffix Automaton）

2026-04-25 赤色 / Phase 8 ★★★★★★★★ Suffix Automaton

問題

文字列 S と Q 個のクエリが与えられる。各クエリ $t_i$ に対し、$t_i$ が S の部分文字列として何回出現するかを答えよ。

制約

$1 \le |S| \le 2 \times 10^5$
$1 \le Q \le 10^5$
$\sum |t_i| \le 5 \times 10^5$
S, t_i は小文字英字

入出力例

入力例 1

abcabc
3
ab
bc
abc

出力例 1

2
2
2

ヒント (段階的開示)

ヒント1: 方向性
Suffix Automaton（SAM）は S の全部分文字列を O(|S|) で表現するオートマトン。各ノードが等価クラス。
ヒント2: アプローチ
1. SAM 構築 O(|S|)／2. cnt（出現回数）を suffix link 木で伝播／3. クエリを SAM 上でたどる。
ヒント3: 誘導
新ノード cur は cnt=1、clone ノードは cnt=0。len 降順で suffix link を辿って cnt を加算。

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

class SAM:
    def __init__(self, n):
        self.MAXN = 2 * n + 5
        self.len = [0] * self.MAXN
        self.link = [-1] * self.MAXN
        self.trans = [dict() for _ in range(self.MAXN)]
        self.cnt = [0] * self.MAXN
        self.size = 1
        self.last = 0

    def extend(self, c):
        if c in self.trans[self.last]:
            q = self.trans[self.last][c]
            if self.len[q] == self.len[self.last] + 1:
                self.last = q
                return
            clone = self.size; self.size += 1
            self.len[clone] = self.len[self.last] + 1
            self.link[clone] = self.link[q]
            self.trans[clone] = dict(self.trans[q])
            self.cnt[clone] = 0
            p = self.last
            while p != -1 and self.trans[p].get(c) == q:
                self.trans[p][c] = clone
                p = self.link[p]
            self.link[q] = clone
            self.last = clone
            return
        cur = self.size; self.size += 1
        self.len[cur] = self.len[self.last] + 1
        self.cnt[cur] = 1
        p = self.last
        while p != -1 and c not in self.trans[p]:
            self.trans[p][c] = cur
            p = self.link[p]
        if p == -1:
            self.link[cur] = 0
        else:
            q = self.trans[p][c]
            if self.len[q] == self.len[p] + 1:
                self.link[cur] = q
            else:
                clone = self.size; self.size += 1
                self.len[clone] = self.len[p] + 1
                self.link[clone] = self.link[q]
                self.trans[clone] = dict(self.trans[q])
                self.cnt[clone] = 0
                while p != -1 and self.trans[p].get(c) == q:
                    self.trans[p][c] = clone
                    p = self.link[p]
                self.link[q] = clone
                self.link[cur] = clone
        self.last = cur

def solve():
    S = input().strip()
    n = len(S)
    sam = SAM(n)
    for c in S:
        sam.extend(c)
    order = sorted(range(sam.size), key=lambda x: -sam.len[x])
    for v in order:
        if sam.link[v] != -1:
            sam.cnt[sam.link[v]] += sam.cnt[v]
    Q = int(input())
    for _ in range(Q):
        t = input().strip()
        cur = 0
        ok = True
        for c in t:
            if c in sam.trans[cur]:
                cur = sam.trans[cur][c]
            else:
                ok = False
                break
        print(sam.cnt[cur] if ok else 0)

solve()

Step-by-Step 解説

1SAM 構築
各文字を extend で追加。新ノード cur の cnt=1、clone は cnt=0。
2出現回数の伝播
suffix link 木で子→親方向に cnt を加算（len 降順）。
3クエリ処理
クエリ t を SAM 上でたどり、到達ノードの cnt が答え。遷移切れたら 0。

よくあるミス

ミス原因正しい書き方
clone の cnt を 1clone は複製cnt[clone] = 0
伝播方向が逆親→子に加算子→親（len 降順）
初期ノード cntroot は 0cnt[0] = 0

次のステップ

  • 2文字列の最長共通部分文字列を SAM で
  • Palindrome Automaton（PAM）

自己評価

自分の回答

気づき・メモ