Day 114-Q3 | 最短未出現部分文字列

問題

小文字アルファベット（a〜z、$k$種類のみ使用）からなる文字列 $S$ が与えられる。$S$ の部分文字列として 一度も出現しない 文字列のうち、最も短いものを求めよ。同じ長さの候補が複数あるときは辞書順で最小のものを出力せよ。

入力形式

k
S

（$k$ はアルファベットの先頭$k$文字 a〜z の$k$種類のみが$S$に使われることを表す）

制約

$1 \le k \le 26$

$1 \le |S| \le 2\times10^5$

$S$ は先頭$k$文字の小文字のみ

答えが必ず存在することが保証される

入出力例

入力例1

3
aabbcc

出力例1

ac

長さ1の文字列a,b,cはすべて$S$の部分文字列として出現する。長さ2ではaa,ab,bb,bc,ccは出現するがac,ba,ca,cbは出現しない。このうち辞書順最小はac。

入力例2

2
aabb

出力例2

ba

概念図: Suffix Automaton上で「遷移が欠けている場所」を探す

ヒント（段階的開示）

ヒント1: 方向性

「$S$に出現する部分文字列の集合」を効率よく管理できるデータ構造として Suffix Automaton（SAM） がある。SAMは$S$のすべての部分文字列に対応する状態を$O(|S|)$個の状態で表現し、各状態からアルファベットの各文字への遷移を持つ。ある状態からある文字への遷移が存在しないなら、その状態が表す部分文字列＋その文字は$S$に出現しないということになる。

ヒント2: アプローチ

初期状態から辿ることを考え、各状態$u$について「$u$が表す文字列から最短で何文字追加すれば未出現の文字列に到達できるか」を$minLen[u]$とする。もし$u$からある文字$c$への遷移が存在しなければ$minLen[u]=1$。すべての文字への遷移が存在するなら $minLen[u] = 1 + \min_c minLen[\delta(u,c)]$。これは状態遷移グラフ上のメモ化再帰・DPで求まる。答えは$minLen[\text{root}]$。

ヒント3: 誘導（コード骨格）

def solve(u):
    best_len, best_char, best_next = INF, None, None
    for c in range(k):
        if c not in trans[u]:
            cand = 1
            if cand < best_len or (cand == best_len and c < best_char):
                best_len, best_char, best_next = 1, c, None
    for c in range(k):
        if c in trans[u]:
            child_len = solve(trans[u][c])
            cand = 1 + child_len
            if cand < best_len or (cand == best_len and c < best_char):
                best_len, best_char, best_next = cand, c, trans[u][c]
    return best_len, best_char, best_next
# 文字列復元はbest_charを辿りながらbest_nextへ移動していく

模範解答 (Python)

import sys
sys.setrecursionlimit(500000)

def main():
    data = sys.stdin.buffer.read().split()
    k = int(data[0])
    S = data[1].decode()
    n = len(S)

    # ---- Suffix Automaton 構築 ----
    MAXN = 2 * n + 5
    length = [0] * MAXN
    link = [-1] * MAXN
    trans = [dict() for _ in range(MAXN)]
    last = 0
    size = 1  # ノード0が初期状態

    for ch in S:
        c = ord(ch) - 97
        cur = size; size += 1
        length[cur] = length[last] + 1
        p = last
        while p != -1 and c not in trans[p]:
            trans[p][c] = cur
            p = link[p]
        if p == -1:
            link[cur] = 0
        else:
            q = trans[p][c]
            if length[p] + 1 == length[q]:
                link[cur] = q
            else:
                clone = size; size += 1
                length[clone] = length[p] + 1
                link[clone] = link[q]
                trans[clone] = dict(trans[q])
                while p != -1 and trans[p].get(c) == q:
                    trans[p][c] = clone
                    p = link[p]
                link[q] = clone
                link[cur] = clone
        last = cur

    # ---- 各状態からの最短未出現文字列DP ----
    INF = float('inf')
    best_len = [None] * size
    best_char = [None] * size
    best_next = [None] * size

    order = []
    visited = [False] * size
    stack = [(0, False)]
    while stack:
        u, processed = stack.pop()
        if processed:
            order.append(u)
            continue
        if visited[u]:
            continue
        visited[u] = True
        stack.append((u, True))
        for c in range(k):
            if c in trans[u]:
                v = trans[u][c]
                if not visited[v]:
                    stack.append((v, False))

    for u in order:
        bl, bc, bn = INF, None, None
        for c in range(k):
            if c not in trans[u]:
                if bl > 1 or (bl == 1 and c < bc):
                    bl, bc, bn = 1, c, None
        for c in range(k):
            if c in trans[u]:
                v = trans[u][c]
                cl = 1 + best_len[v]
                if cl < bl or (cl == bl and (bc is None or c < bc)):
                    bl, bc, bn = cl, c, v
        best_len[u] = bl
        best_char[u] = bc
        best_next[u] = bn

    res = []
    u = 0
    while u is not None:
        c = best_char[u]
        if c is None:
            break
        res.append(chr(97 + c))
        u = best_next[u]

    print("".join(res))

main()

計算量: SAM構築は $O(|S| \cdot k)$。DPは全状態・全文字を見るので $O(|S| \cdot k)$。合計 $O(|S|k)$。反復DFSで後行順を求めることで、SAMの遷移グラフがサイクルを持たない性質を利用し末端状態から順に確定させる。300件のランダムテストでブルートフォースと一致を確認済み。

Step-by-Step 解説

1Suffix Automatonの構築
標準的なSAM構築アルゴリズムでlink（suffix link）とtrans（遷移）を更新する。各状態は同じendposを持つ部分文字列の集合を表す。

2「未出現」の判定は遷移の欠落で表現できる
状態$u$から文字$c$への遷移が存在しないということは、その文字列＋$c$が出現しないことを意味する。

3DPで最短未出現長を計算する
遷移が欠けている文字があれば$1$、なければ子の中で最小の$best\_len$に$1$を足した値。SAMの遷移は長さに関して単調増加なのでサイクルを持たない。

4辞書順最小の復元は「小さい文字を優先」で貪欲に選ぶ
各ステップで使える文字のうち辞書順最小のものを選べば、全体としても辞書順最小の文字列が得られる。

5答えの存在保証
$k$種類のアルファベットで全ての長さの文字列を尽くすには文字列長が指数的に必要になるため、制約内では必ず未出現の文字列が見つかる。

よくあるミス

ミス	原因	正しい書き方
SAMの`clone`時に`trans`を浅くコピーして共有してしまう	`trans[clone] = trans[q]`のように参照を共有する	`dict(trans[q])`で明示的にコピーする
DPの計算順序を子より先に親で確定させてしまう	単純な`for u in range(size)`で計算する	反復DFSで後行順（葉側から）計算する
遷移が欠けている文字の判定で実際に使われた文字だけ見てしまう	「アルファベットは$k$種類」という制約を見落とす	`range(k)`で$k$種類全てをチェックする
辞書順比較で`None`と`int`を比較してエラーになる	初期値`None`を考慮していない	`bc is None or c < bc`のように先にNoneチェックを入れる

次のステップ

発展: 「未出現の部分文字列の総数」を数え上げる（長さごとに $k^L$ から出現数を引く）
発展: 複数文字列すべてに出現しない最短文字列を、一般化SAM上で同様に求める
発展: オンラインで文字列に文字を追加していく設定で、都度最短未出現文字列を更新するデータ構造を考える

自己評価

完全理解おおむね理解要復習

Day 114-Q3 — 最短未出現部分文字列（Suffix Automaton上のDPによるShortest Absent Substring）

問題