問題
文字列 $S$（長さ $N$、英小文字のみ）が与えられる。
Weiner のアルゴリズムは、接尾辞木を右から左へ、すなわち「$S$ の最後の文字だけからなる接尾辞」→「最後の2文字」→ … → 「$S$ 全体」の順に、1文字ずつ先頭に追加しながらオンラインに構築していく古典的な手法である（Ukkonen法が左から右に1文字ずつ「末尾に追加」するのと対照的な方向性を持つ）。
この問題では、簡略化のため「圧縮されていない接尾辞トライ（各エッジが1文字に対応する素朴なトライ木）」を、Weiner 法と同じ右から左への挿入順序で構築する。すなわち、
- ステップ1: $S[N-1:]$（最後の1文字）をトライに挿入する
- ステップ2: $S[N-2:]$（最後の2文字）をトライに挿入する
- …
- ステップN: $S[0:]$（$S$ 全体）をトライに挿入する
とし、各ステップ終了時点でのトライの総ノード数（根を除く）を出力せよ。同じパスが既に存在する場合はノードを再利用し、新しく分岐する部分のみノードを追加する。
入力形式
S制約
入出力例
入力例1
aab出力例1
1 3 5入力例2
aaa出力例2
1 2 3概念図
ヒント（段階的開示）
ヒント1（方向性）
トライ木への文字列挿入は、通常「左から右」に1文字ずつ辿りながら子ノードを作る操作として習う。この問題ではそれを「短い接尾辞から長い接尾辞へ」という時間軸の上で繰り返し行う点が特徴である。過去に挿入した接尾辞と共通する接頭辞がある場合、途中まではノードが再利用され、共通しなくなった地点から新しいノードが分岐する。
ヒント2（アプローチ）
各ステップで挿入する文字列は「現在のトライのルートから、その接尾辞の文字を1文字ずつ順にたどる」ことで処理できる。たどる途中で既存の子ノードがあればそれを使い、なければ新規ノードを1つ作ってノード数カウンタを1増やす、という操作を素直に実装すればよい。$N \le 2000$ なので、1回の挿入に $O(N)$ かけても全体で $O(N^2)$ となり、十分高速に動作する。
ヒント3（誘導）
children = [dict()] # children[0] がルート
node_count = 0
results = []
for i in range(n - 1, -1, -1):
cur = 0
for ch in s[i:]:
if ch in children[cur]:
cur = children[cur][ch]
else:
children.append(dict())
new_idx = len(children) - 1
children[cur][ch] = new_idx
cur = new_idx
node_count += 1
results.append(node_count)最終的な node_count（最後のステップの値）は、文字列 $S$ に含まれる相異なる非空部分文字列の総数と一致する。これは「トライの各ノードが根からの経路として表す文字列と1対1対応する」ことから従う自然な帰結である。
模範解答 (Python)
import sys
def main():
s = sys.stdin.readline().strip()
n = len(s)
children = [dict()]
node_count = 0
results = []
for i in range(n - 1, -1, -1):
cur = 0
suffix = s[i:]
for ch in suffix:
nxt = children[cur].get(ch)
if nxt is None:
children.append(dict())
nxt = len(children) - 1
children[cur][ch] = nxt
node_count += 1
cur = nxt
results.append(node_count)
print(' '.join(map(str, results)))
main()Step-by-Step 解説
Weiner のアルゴリズムの本質は、「$S$ の接尾辞すべて」を扱う構造を、1文字を文字列の先頭に追加するという操作だけでオンラインに更新し続けられる点にある。$S'=c+S$ としたとき、$S'$ の接尾辞集合は「$S$ の接尾辞集合すべて」と「$S'$ 自身（新しい接尾辞）」の和集合になる。右端から左へ処理を進めることは、常に「今処理した部分文字列全体を新しい接尾辞として追加する」ことに対応し、過去に追加した接尾辞は不変のまま保持される。
各ステップで行うのは「現在のステップの接尾辞1本を、既存のトライに（可能な限り既存パスを再利用しながら）挿入する」という操作のみ。過去に追加した接尾辞のパスを壊す必要は一切ない（トライは追記専用の構造）。
新規ノードを作るのは「今までにこの接頭辞パスが一度も出現していなかった」場合のみである。したがって、ある時点でのノード総数は「これまでに挿入したすべての接尾辞に含まれる、相異なる非空接頭辞（＝相異なる部分文字列）の総数」に正確に一致する。
真の Weiner 法は、単純なパス（分岐のない一本道）を1つの辺のラベル（範囲
[l, r)）にまとめることで、ノード数を $O(N)$ に抑える。さらに「narrow search」「wide search」と呼ばれる、既存の木構造上の特定位置を高速に見つけるための手続きを使うことで、全体を償却 $O(N)$（アルファベットサイズ固定）で構築する。本問では学習のためにあえて圧縮を行わず、素朴なトライのままノード数の増加を観察することで、「右から左へのオンライン挿入」という構築順序の直感を掴むことを目的としている。1回の挿入に $O(|S[i:]|)$、全体で $\sum_{i=0}^{N-1}(N-i)=O(N^2)$。$N\le2000$ の制約下では最悪でも約 $2\times10^6$ 回程度の操作で済み、十分高速。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 挿入順序を左から右（Ukkonen式）にしてしまう | 接尾辞木というと Ukkonen 法のイメージが強く、方向を意識しない | 本問は「短い接尾辞→長い接尾辞」の順、すなわち文字列の右端から左端へ向かう順序で処理する |
| 各ステップのノード数を「そのステップで新規作成した数」だけ出力してしまう | 累積カウントと増分カウントを混同する | node_count は毎ステップ加算されていく累積値であり、それをそのまま出力する |
| ルートノードもノード数に含めてしまう | カウント初期値を1（ルート込み）にしてしまう | ルートは常にカウント対象外とし、初期値は0にする |
| 同じ文字が連続する文字列（例: "aaa"）で毎回新規ノードを作ってしまう | 子ノード探索を dict ではなく毎回新規作成のロジックで書いてしまう | children[cur].get(ch) で既存ノードの有無を必ず確認してから新規作成する |
| 出力例1が合わない場合、文字コードの扱いミスを疑いがち | 実際は「累積ノード数の数え方」を誤っていることが多い | 小さな例（"aab" など）を手で1ステップずつトレースして確認する |
次のステップ
- 発展: 本問のトライを「一本道のパスを1つの辺にまとめる」形に圧縮し、真の接尾辞木（ノード数 $O(N)$）を構築するプログラムに拡張せよ。圧縮後のノード数が、Ukkonen法で構築した場合と一致することを確認せよ。
- 発展2: 出力される最終値（全ステップ終了後のノード数）が、Suffix Automaton や Suffix Array + LCP 配列から計算した「相異なる部分文字列の総数」の公式と一致することを別解として確認し、3通りの手法の答えが一致することを検証せよ。