問題
文字列 $S$ に対して以下のクエリを処理:
COUNT: 異なる部分文字列の総数KQUERY k: 辞書順 $k$ 番目の部分文字列
制約
$1 \le |S| \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$
$1 \le k \le 10^{18}$
入出力例
入力例 1
aab
3
COUNT
KQUERY 1
KQUERY 5出力例 1
5
a
baab の異なる部分文字列: a, aa, aab, ab, b の5個。
ヒント (段階的開示)
ヒント1: 方向性
Suffix Automaton (SAM) を構築。各状態 $v$ が表す部分文字列数 = $len[v] - len[link[v]]$。
ヒント2: アプローチ
SAM を DAG とみなし、トポロジカル順（len 降順）に
dp[v] = v 以降到達可能な文字列数を計算。$k$ 番目は遷移を a→z 順に試して貪欲に降りる。ヒント3: 誘導
root の
dp[0] は空文字列を含むため -1 調整。模範解答 (Python)
import sys
from sys import stdin
input = stdin.readline
def solve():
S = input().strip()
n = len(S)
MAXN = 2 * n + 5
nxt = [[-1] * 26 for _ in range(MAXN)]
link = [-1] * MAXN
length = [0] * MAXN
last = 0
size = 1
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
nxt[clone] = nxt[q][:]
link[clone] = link[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) - ord('a'))
order = sorted(range(size), key=lambda v: -length[v])
dp = [0] * size
for v in order:
dp[v] = 1
for c in range(26):
nv = nxt[v][c]
if nv != -1:
dp[v] += dp[nv]
dp[0] -= 1
total = sum(dp[nxt[0][c]] for c in range(26) if nxt[0][c] != -1)
def kth_query(k):
v = 0
result = []
while k > 0:
for c in range(26):
nv = nxt[v][c]
if nv == -1:
continue
if dp[nv] >= k:
result.append(chr(ord('a') + c))
v = nv
k -= 1
break
else:
k -= dp[nv]
return ''.join(result)
Q = int(input())
out = []
for _ in range(Q):
line = input().split()
if line[0] == 'COUNT':
out.append(str(total))
else:
out.append(kth_query(int(line[1])))
print('\n'.join(out))
solve()Step-by-Step 解説
1SAM 構築
各文字を
各文字を
sa_extend で追加。状態は $O(|S|)$、各状態は等価クラスの部分文字列を代表。2DAG DP
length 降順に
length 降順に
dp[v] = 1 + sum dp[nxt[v][c]]。root は空文字列を含むため $-1$。3COUNT
root の遷移先の dp 和。または $\sum_{v \ne 0} (len[v] - len[link[v]])$。
root の遷移先の dp 和。または $\sum_{v \ne 0} (len[v] - len[link[v]])$。
4KQUERY
root から a→z 順に試し、
root から a→z 順に試し、
dp[nv] >= k なら進んで k -= 1、そうでなければ k -= dp[nv]。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| root の dp を -1 しない | 空文字列を含む | dp[0] -= 1 |
| k 減算 off-by-one | 遷移時の消費忘れ | 遷移後 k -= 1 |
| clone 作成時の nxt コピー忘れ | clone は q の遷移を引き継ぐ | nxt[clone] = nxt[q][:] |
次のステップ
- Generalized SAM で複数文字列の共通部分文字列数
- Suffix Array + LCP との比較