問題
文字列 $S$（小文字英字のみ）が与えられる。$S$ の相異なる部分文字列（空文字列を除く）をすべて辞書順に並べたとき、K番目に小さいものを出力せよ。そのようなK番目の部分文字列が存在しない場合は -1 を出力せよ。
入力形式
S
K制約
$1 \le |S| \le 1000$
$S$ は小文字英字のみ
$1 \le K \le 10^{18}$
入出力例
入力例1
aab
3出力例1
aabS="aab"の相異なる部分文字列は{a, aa, aab, ab, b}の5個。辞書順に並べると a, aa, aab, ab, b となり、3番目は"aab"。
入力例2
aab
6出力例2
-1相異なる部分文字列は5個しかないのでK=6は存在しない。
概念図: SAM遷移DAG上のways集計とK番目探索
ヒント（段階的開示）
ヒント1: 方向性
$|S|\le1000$なので相異なる部分文字列は最大で約$|S|^2/2$個存在しうる。すべて列挙してソートするO(N²logN)解法でも間に合う場合はあるが、Suffix Automaton（SAM）を使うとO(N)〜O(N·Σ)で解ける。SAMは根から各状態への遷移パスと相異なる部分文字列を重複なく1対1対応させるデータ構造である。
ヒント2: アプローチ
各状態vについて「vそのものに到達する部分文字列」1個＋「さらに遷移を続けて作れる部分文字列」の個数を再帰的に数えれば、状態ごとの部分木サイズ（ways[v]）が求まる。あとは根からwaysの値を使って貪欲に「K番目はどの文字から始まるか」を絞り込んでいけばよい。
ヒント3: 誘導（コード骨格）
order = sorted(range(size), key=lambda x: -length[x])
ways = [0]*size
for v in order:
w = 1
for c, to in trans[v].items():
w += ways[to]
ways[v] = w
ways[0] -= 1 # 根(空文字列)の補正
total = ways[0]
if K > total:
print(-1)
else:
cur = 0; remaining = K; res = []
while remaining > 0:
for c in sorted(trans[cur]):
to = trans[cur][c]
block = ways[to]
if remaining <= block:
res.append(c); cur = to; remaining -= 1
break
else:
remaining -= block
print(''.join(res))模範解答 (Python)
import sys
def solve():
data = sys.stdin.buffer.read().split()
S = data[0].decode()
K = int(data[1])
n = len(S)
MAXN = 2 * n + 5
length = [0] * MAXN
link = [-1] * MAXN
trans = [dict() for _ in range(MAXN)]
size = 1
last = 0
def sa_extend(c):
nonlocal size, last
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
for ch in S:
sa_extend(ch)
order = sorted(range(size), key=lambda x: -length[x])
ways = [0] * size
for v in order:
w = 1
for c, to in trans[v].items():
w += ways[to]
ways[v] = w
ways[0] -= 1
total = ways[0]
if K > total:
print(-1)
return
cur = 0
remaining = K
res = []
while remaining > 0:
for c in sorted(trans[cur].keys()):
to = trans[cur][c]
block = ways[to]
if remaining <= block:
res.append(c)
cur = to
remaining -= 1
break
else:
remaining -= block
print(''.join(res))
solve()計算量: SAM構築はO(N)（状態数は高々2N）、waysの計算は全遷移を1回ずつ見るのでO(N)、K番目探索は解の長さ≤N回のループでそれぞれアルファベットサイズ(≤26)分の遷移を調べるのでO(26N)。乱数300試行のstress test（全部分文字列を愚直に列挙・ソートするbrute forceとの突き合わせ、K=1・K=total・K=total+1などの境界値も含む）を実際に実行し、全試行で一致・境界値-1判定ともに確認済み。
Step-by-Step 解説
1SAMの各状態は「終端位置集合」を表す
本問で重要なのは「根から各状態への遷移パス＝1つの相異なる部分文字列」という対応関係である。
本問で重要なのは「根から各状態への遷移パス＝1つの相異なる部分文字列」という対応関係である。
2遷移DAG上のパス数え上げ
根からある頂点までの経路は、SAM構築の性質上ちょうど1つの相異なる部分文字列に対応する。相異なる部分文字列の総数は根から到達可能な全頂点への到達パス数の総和に等しい。
根からある頂点までの経路は、SAM構築の性質上ちょうど1つの相異なる部分文字列に対応する。相異なる部分文字列の総数は根から到達可能な全頂点への到達パス数の総和に等しい。
3ways[v]の意味
ways[v] = 1 + Σ ways[to] という単純なDAG上のDPで求まる。根だけは空文字列という無効な打ち切りを1回分余分に含むので最後に1を引いて補正する。
ways[v] = 1 + Σ ways[to] という単純なDAG上のDPで求まる。根だけは空文字列という無効な打ち切りを1回分余分に含むので最後に1を引いて補正する。
4K番目を貪欲に絞り込む
現在位置から遷移できる文字を辞書順に試す。Kがways[to]以下なら答えはこの遷移の先にあると確定し、そうでなければKからways[to]を引いて次の文字を試す。
現在位置から遷移できる文字を辞書順に試す。Kがways[to]以下なら答えはこの遷移の先にあると確定し、そうでなければKからways[to]を引いて次の文字を試す。
5なぜ「接頭辞+c自身」が常にブロックの先頭か
「接頭辞+c」はそれを伸ばした文字列すべての真の接頭辞であり、辞書順比較では真の接頭辞の方が必ず小さいので、そのブロック内で辞書順最小になる。
「接頭辞+c」はそれを伸ばした文字列すべての真の接頭辞であり、辞書順比較では真の接頭辞の方が必ず小さいので、そのブロック内で辞書順最小になる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 根のwaysから空文字列分の-1補正を忘れる | 根も他の状態と同じ扱いで計算してしまう | ループ後にways[0]-=1を必ず行う |
| K番目探索で文字を辞書順ではなくdictの挿入順のまま調べてしまう | Pythonのdictが挿入順を保持することに頼ってしまう | 必ずsorted(trans[cur].keys())で明示的にソートする |
| remaining<=blockではなくremaining<blockで判定してしまう | ブロックの最初の要素を含めるかどうかを誤る | 接頭辞+c自身を選ぶケースを含めるため<=が正しい |
| clone状態のtransを浅いコピーではなく参照共有にしてしまう | trans[clone]=trans[q]と書いて同じ辞書を共有してしまう | 必ずdict(trans[q])のように複製する |
次のステップ
- 発展: K番目の部分文字列だけでなく「与えられた部分文字列が辞書順で何番目か」を逆算するクエリにも対応させる。
- 次回予告: 回転キャリパー法（凸多角形の直径）