問題
文字列 $S$（長さ $N$）と整数 $K$（$1 \le K \le 26$）が与えられる。$S$ はアルファベットの先頭 $K$ 文字のみからなる。
$S$ の部分文字列として一度も出現しない文字列（アルファベットは同じく先頭 $K$ 文字のみ使用可）のうち、最短で、同じ長さの候補が複数あるなら辞書順最小のものを求めよ。
（長さ $L$ の文字列は $K^L$ 通り存在し、$S$ の相異なる部分文字列は高々 $\frac{N(N+1)}{2}$ 個しかないため、答えは必ず有限の長さで求まることが保証される）
入力形式
N K
S制約
入出力例
入力例1
4 2
abab出力例1
aa長さ1の "a","b" はどちらも出現。長さ2の "ab","ba" は出現するが "aa","bb" は出現しない。辞書順最小は "aa"
入力例2
2 2
aa出力例2
b"b" 自体が1文字も出現していないので、長さ1で答えが決まる
入力例3
1 1
a出力例3
aaアルファベットは "a" のみ。長さ1の "a" は出現済みなので長さ2の "aa" が答え
概念図
ヒント（段階的開示）
ヒント1（方向性）
すべての部分文字列を陽に列挙して集合に入れ、短い文字列から順に $K^L$ 通り全探索して判定する方法は $O(N \cdot K^L)$ 程度かかり、$L$ が大きくなると間に合わない。$S$ の部分文字列全体を効率よく管理できるデータ構造として、Suffix Automaton（接尾辞オートマトン）の遷移構造そのものを「文字列 → 状態」の対応表とみなせないかを考える。
ヒント2（アプローチ）
Suffix Automatonは、初期状態（root）から文字を1つずつ辿る遷移 next[state][c] を持ち、root から辿り着ける遷移パスはちょうど $S$ の部分文字列全体（空文字列含む）に1対1で対応する。したがって、rootから幅優先探索（BFS）で遷移をたどり、ある状態からある文字 $c$ への遷移が存在しない瞬間を捉えれば、そこまでのパス文字列 + $c$ が「$S$ の部分文字列として出現しない」文字列になる。BFSなので最初に見つかったものが最短、かつ同じ深さの中で文字を 'a' から順に試せば辞書順最小も同時に保証される。
ヒント3（誘導）
BFSでは文字列そのものを持ち回らず、各状態に「どの状態から」「どの文字で」到達したか（parent, pchar）だけを記録し、見つかった時点で逆順にたどって復元するとメモリ・時間が節約できる。
from collections import deque
visited = [False] * size
visited[0] = True
parent = [-1] * size
pchar = [-1] * size
dq = deque([0])
while dq:
u = dq.popleft()
for c in range(K):
v = nxt[u][c]
if v == -1:
# ここで S の部分文字列にない文字列が見つかる
...
elif not visited[v]:
visited[v] = True
parent[v] = u
pchar[v] = c
dq.append(v)模範解答 (Python)
import sys
from collections import deque
def solve():
data = sys.stdin.read().split()
n = int(data[0])
k = int(data[1])
s = data[2]
MAXN = 2 * n + 5
length = [0] * MAXN
link = [-1] * MAXN
nxt = [[-1] * k for _ in range(MAXN)]
size = 1
last = 0
def sa_extend(c):
nonlocal last, size
cur = size
size += 1
length[cur] = length[last] + 1
p = last
while p != -1 and nxt[p][c] == -1:
nxt[p][c] = cur
p = link[p]
if p == -1:
link[cur] = 0
else:
q = nxt[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]
nxt[clone] = nxt[q][:]
while p != -1 and nxt[p][c] == q:
nxt[p][c] = clone
p = link[p]
link[q] = clone
link[cur] = clone
last = cur
for ch in s:
sa_extend(ord(ch) - 97)
visited = [False] * size
visited[0] = True
parent = [-1] * size
pchar = [-1] * size
dq = deque([0])
found_u = -1
found_c = -1
while dq and found_u == -1:
u = dq.popleft()
for c in range(k):
v = nxt[u][c]
if v == -1:
found_u = u
found_c = c
break
if not visited[v]:
visited[v] = True
parent[v] = u
pchar[v] = c
dq.append(v)
path = [found_c]
u = found_u
while u != 0:
path.append(pchar[u])
u = parent[u]
path.reverse()
print(''.join(chr(97 + c) for c in path))
solve()Step-by-Step 解説
Suffix Automaton は $S$ の全ての部分文字列（空文字列含む）を、rootから始まる遷移パスとして過不足なく表現するオートマトンである。状態数・遷移数はともに $O(N)$ に収まる。ある文字列 $T$ が $S$ の部分文字列である $\iff$ root から $T$ の各文字をたどって遷移が最後まで存在する。
「$S$ の部分文字列でない最短文字列」を求めることは、「root から遷移をたどっていって、ある文字で遷移が存在しなくなる、最も浅い（＝最短）分岐点」を探すことと同値である。BFSは深さの浅い順に状態を処理するため、最初に遷移欠損を見つけた時点が最短の答えを与える。
各状態の子を処理する際、文字を 'a' から順に試すことで、同じ深さのBFSレベル内で「どの文字列がキューに先に入るか」が辞書順と一致する。これにより、同じ長さの中で最初に見つかった遷移欠損が辞書順最小のものになる。
文字列を都度連結すると計算コストがかさむため、
parent（どの状態から来たか）と pchar（どの文字で来たか）だけを保存し、答えが見つかった時点で逆順にたどって $O(\text{答えの長さ})$ で復元する。Suffix Automaton構築は $O(N \cdot K)$、BFSも全状態・全文字を高々1回ずつ調べるので $O(N \cdot K)$。合計 $O(NK)$ で、$N \le 2\times10^5$, $K \le 26$ でも十分高速に動作する。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 文字列を都度連結してBFSする | 計算量を軽視 | parent/pchar で経路だけ保存し最後に復元する |
| DFSで探索してしまう | 「最短」を優先度探索と誤解 | 必ずBFS（幅優先）を使う。深さの浅い順に処理することが最短性の根拠 |
| クローン状態を遷移DAGの対象から除外してしまう | クローン状態は「本物の文字列に対応しない」という誤解 | クローン状態も実在の部分文字列に対応するため、通常の状態と同様にBFSの対象に含める |
| $K$ 未満の文字だけ調べて次の文字を見落とす | ループ範囲を26固定にしてしまう | 必ず入力の $K$ の範囲でループする（range(K)） |
次のステップ
- 発展: 答えの文字列の個数（同じ長さの非出現文字列が何通りあるか）を求める問題に拡張できる。BFSの最初のレベルで遷移欠損が複数見つかった場合にすべて数え上げればよい。
- 次回予告: 区間グラフの彩色（Interval Graph Coloring・完全グラフ性質を用いた最小色数の構成）