Day 086-Q1 — Suffix Automaton（相異なる部分文字列の個数・SAM・$O(N)$）

問題

英小文字からなる文字列 $S$ が与えられる。$S$ の空でない相異なる部分文字列の個数を求めよ。

入出力例

abab

7

部分文字列は a, b, ab, ba, aba, bab, abab の 7 種類。

概念図: SAM の状態と長さ区間の寄与

ヒント

# online 構築 + clone 処理（len[p]+1 != len[q] のとき）
ans = sum(length[v] - length[link[v]] for v in range(1, sz))

模範解答

import sys

def solve():
    S = sys.stdin.readline().strip()
    N = len(S)
    MAX = 2 * N + 5
    nxt = [dict() for _ in range(MAX)]
    link = [0] * MAX
    length = [0] * MAX
    link[0] = -1
    last = 0
    sz = 1
    for ch in S:
        cur = sz; sz += 1
        length[cur] = length[last] + 1
        p = last
        while p != -1 and ch not in nxt[p]:
            nxt[p][ch] = cur
            p = link[p]
        if p == -1:
            link[cur] = 0
        else:
            q = nxt[p][ch]
            if length[p] + 1 == length[q]:
                link[cur] = q
            else:
                clone = sz; sz += 1
                length[clone] = length[p] + 1
                nxt[clone] = dict(nxt[q])
                link[clone] = link[q]
                while p != -1 and nxt[p].get(ch) == q:
                    nxt[p][ch] = clone
                    p = link[p]
                link[q] = clone
                link[cur] = clone
        last = cur
    ans = 0
    for v in range(1, sz):
        ans += length[v] - length[link[v]]
    print(ans)

solve()

計算量: 状態数・遷移数ともに $O(N)$、構築 $O(N \cdot |\Sigma|)$（dict 使用で実質 $O(N)$）。

Step-by-Step 解説

Step 1: SAM の状態と endpos

各状態は endpos（出現終端位置集合）が等しい文字列の同値類。同値類内の長さは連続区間 $(\text{len}[\text{link}[v]], \text{len}[v]]$。

Step 2: online 構築

文字を 1 つずつ追加し、新状態 `cur` を作って `last` から suffix link を辿り遷移を張る。

Step 3: clone 処理

Step 4: 部分文字列数の集計

各状態 $v$ は $\text{len}[v] - \text{len}[\text{link}[v]]$ 個の新規部分文字列を担う。総和が答え。

よくあるミス

次のステップ

• 発展問題: 各部分文字列の出現回数総和（endpos サイズ × 長さ、suffix link 木上の累積）
• 発展問題: 辞書順 $k$ 番目の相異なる部分文字列（SAM 上の DAG DP + 貪欲）

自己評価