問題
文字列 $S$（英小文字のみ、長さ $N$）が与えられる。$S$ の末尾に番兵文字 $ を付加し、Ukkonenのアルゴリズムを用いてSuffix Tree（接尾辞木）を $O(N)$ で構築せよ。
構築後、次の2つを出力せよ。
- $S$ の相異なる非空部分文字列の個数
- $S$ 中に2回以上出現する部分文字列のうち最長のものの長さ（存在しなければ
0）。同じ長さの候補が複数あれば辞書順最小のものの長さで良い（長さのみ出力するので実質関係ない）
入力形式
S制約
$1 \le |S| \le 100000$
$S$ は英小文字のみ
入出力例
入力例1
banana出力例1
15
3banana の相異なる部分文字列は15個。最長重複部分文字列は ana（長さ3）
入力例2
abcde出力例2
15
0全部異なる文字なので重複部分文字列は存在しない
概念図
ヒント（段階的開示）
ヒント1（方向性）
すべての接尾辞をトライ木に愚直に挿入すると $O(N^2)$ のノード数になってしまう。共通の接頭辞をパス圧縮（1本道はまとめて1本の辺にする）すれば全体で $O(N)$ ノードに収まるはずだが、「文字を1文字ずつ末尾に追加しながら」木を更新する方法が問題になる。全体を再構築せず、すでに構築済みの部分を再利用しながら差分更新するのがUkkonenのアルゴリズムの核心である。
ヒント2（アプローチ）
Ukkonenのアルゴリズムは「フェーズ $i$」で文字 $S[i]$ を追加する際、それまでに存在するすべての接尾辞の末尾に $S[i]$ を延長する「拡張」を行う。素朴には各フェーズで $O(i)$ 個の拡張が必要で全体 $O(N^2)$ になるが、3つのトリック——①リーフの末尾を共有インデックスで管理（一度リーフになった辺は自動で伸びる）、②同じ場所に来たら即座に打ち切る（ルール3）、③サフィックスリンクでジャンプ——を組み合わせることで、償却 $O(N)$ を達成する。active_point（現在の挿入位置）を毎フェーズ間で保持し続けるのがポイント。
ヒント3（誘導）
active_node・active_edge・active_length の3つ組で「次にどこから拡張を始めるか」を表す。1文字追加するたびに以下を行う：
remaining += 1
last_new_internal_node = None
while remaining > 0:
if active_length == 0:
active_edge = i # 現在位置の文字から辺を辿る
if S[active_edge] not in nodes[active_node].children:
# ルール2: 新しいリーフを直接生やす
create_leaf(); remaining -= 1
else:
# 既存の辺を辿る／途中で分岐（split）する
...
# active_node が root なら active_length を1減らして active_edge を進める
# root でなければ suffix link を辿る模範解答 (Python)
import sys
def solve():
s = sys.stdin.readline().strip() + "$"
n = len(s)
# ノードはリストで管理: children(dict), link(int, -1=未設定), start, end(int or None=leaf)
# 注意: 空リストから始める（ダミーの0番ノードを作らない）。root は new_node の最初の呼び出しで作る
children = []
link = []
start_arr = []
end_arr = [] # -1 の場合はグローバル end (leaf_end) を参照する
def new_node(st, en):
children.append({})
link.append(-1)
start_arr.append(st)
end_arr.append(en)
return len(children) - 1
root = new_node(-1, -1)
active_node = root
active_edge = -1
active_length = 0
remaining = 0
leaf_end = -1
last_new_node = -1
def edge_length(node):
e = leaf_end if end_arr[node] == -1 else end_arr[node]
return e - start_arr[node] + 1
for i in range(n):
leaf_end = i
remaining += 1
last_new_node = -1
while remaining > 0:
if active_length == 0:
active_edge = i
ch = s[active_edge]
if ch not in children[active_node]:
# ルール2: 新規リーフ
leaf = new_node(i, -1)
children[active_node][ch] = leaf
if last_new_node != -1:
link[last_new_node] = active_node
last_new_node = -1
else:
nxt = children[active_node][ch]
elen = edge_length(nxt)
if active_length >= elen:
active_edge += elen
active_length -= elen
active_node = nxt
continue
if s[start_arr[nxt] + active_length] == s[i]:
# ルール3: すでに存在する -> 何もせず終了（ここがフェーズ全体を打ち切る鍵）
if last_new_node != -1 and active_node != root:
link[last_new_node] = active_node
last_new_node = -1
active_length += 1
break
# 分岐（split）
split_end = start_arr[nxt] + active_length - 1
split = new_node(start_arr[nxt], split_end)
children[active_node][ch] = split
leaf = new_node(i, -1)
children[split][s[i]] = leaf
start_arr[nxt] += active_length
children[split][s[start_arr[nxt]]] = nxt
if last_new_node != -1:
link[last_new_node] = split
last_new_node = split
remaining -= 1
if active_node == root and active_length > 0:
active_length -= 1
active_edge = i - remaining + 1
elif active_node != root:
active_node = link[active_node]
if active_node == -1:
active_node = root
# --- 相異なる部分文字列の個数 = 全辺の長さの総和（$を含む1本を除く） ---
total_nodes = len(children)
total_distinct = 0
max_depth_internal = 0 # 2回以上出現する部分文字列の最長長さ = 内部ノードの最大深さ
# BFS/DFSで各ノードの文字列深さを計算
depth = [0] * total_nodes
stack = [root]
visited_order = []
while stack:
u = stack.pop()
visited_order.append(u)
for ch, v in children[u].items():
elen = edge_length(v)
depth[v] = depth[u] + elen
stack.append(v)
for u in range(total_nodes):
if u == root:
continue
parent_depth = depth[u] - edge_length(u)
# $ の1文字だけの辺（リーフで深さ1、$のみ）は空文字列由来なので除外調整は不要
# ただし文字列末尾の $ を含む部分文字列は数えない -> 各リーフ辺の末尾から$分を引く
elen = edge_length(u)
if end_arr[u] == -1: # leaf
# このリーフが表す文字列の末尾が $ を含むかチェック
leaf_str_end = leaf_end # 常に n-1
if s[leaf_str_end] == '$':
elen -= 1
total_distinct += elen
if children[u]: # 内部ノード = 分岐がある = 対応する文字列が2回以上出現
max_depth_internal = max(max_depth_internal, depth[u])
print(total_distinct)
print(max_depth_internal)
solve()Step-by-Step 解説
1素朴な構築が $O(N^2)$ になる理由
すべての接尾辞を1本ずつトライに挿入すると、接尾辞の総文字数は $N + (N-1) + \cdots + 1 = O(N^2)$ になる。パス圧縮した木自体はノード数 $O(N)$ に収まるが、構築の途中で毎回どこまで一致しているかを線形に辿ると $O(N^2)$ の作業量がかかってしまう。
すべての接尾辞を1本ずつトライに挿入すると、接尾辞の総文字数は $N + (N-1) + \cdots + 1 = O(N^2)$ になる。パス圧縮した木自体はノード数 $O(N)$ に収まるが、構築の途中で毎回どこまで一致しているかを線形に辿ると $O(N^2)$ の作業量がかかってしまう。
2リーフの自動延長（トリック1）
各フェーズで新しく作ったリーフの終端を、共有変数
各フェーズで新しく作ったリーフの終端を、共有変数
leaf_end（コード中の end_arr[node] == -1 で表現）に固定する。これにより、次フェーズで leaf_end を1つ進めるだけですべての既存リーフが自動的に1文字延長される。これが「一度リーフになった辺はもう明示的に触らなくてよい」というトリック1で、これだけで作業量が大幅に減る。3ルール3による早期終了（トリック2）
拡張しようとした文字がすでに辺上に存在する場合（
拡張しようとした文字がすでに辺上に存在する場合（
s[start+active_length] == s[i]）、そこでそのフェーズの残り拡張をすべてスキップして良いという性質がある（暗黙的にすでに表現されているため）。これにより、1フェーズあたりの実質的な作業が大幅に減る。4サフィックスリンクによるジャンプ（トリック3）
新しい内部ノードを作ったとき、直前に作った内部ノードからサフィックスリンクを張る。次の拡張では
新しい内部ノードを作ったとき、直前に作った内部ノードからサフィックスリンクを張る。次の拡張では
active_node をサフィックスリンク経由で移動することで、毎回ルートから辿り直す必要がなくなる。この3つのトリックの組み合わせにより、償却計算量が $O(N)$（アルファベットサイズを無視すれば）になることが証明されている（Ukkonen, 1995）。5相異なる部分文字列数と最長重複部分文字列
構築済みの木において、ルート以外の全辺の長さの総和が相異なる部分文字列の個数に一致する（番兵
構築済みの木において、ルート以外の全辺の長さの総和が相異なる部分文字列の個数に一致する（番兵
$ を跨ぐ分だけ補正）。また、分岐を持つ内部ノード（=2回以上出現する文字列に対応）の中で文字列深さが最大のものが最長重複部分文字列の長さになる。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| リーフの終端を個別変数で管理し、毎フェーズ全リーフを更新する | トリック1（共有 leaf_end）を理解していない | リーフは end = -1（= グローバル leaf_end を参照）で表現し、更新は1箇所で済ませる |
ルール3で早期終了する際に remaining を減らしてしまう | 「暗黙的にすでに存在する」＝「まだ拡張が完了していない」ことを誤解 | ルール3のときは break するだけで remaining は変えない（次フェーズに持ち越す） |
サフィックスリンクを active_node == root のときにも辿ろうとする | root は特別扱いが必要なことを見落とす | root の場合は active_length を1減らして active_edge を進める、それ以外はリンクを辿る |
番兵 $ を含む部分文字列を距離計算に含めてしまう | 末尾の番兵の役割（構築を完了させるためだけ）を忘れる | リーフ辺の長さから $ の1文字分を引いてから集計する |
次のステップ
- 発展: Ukkonenのアルゴリズムで構築したSuffix TreeにLCA前処理を追加すれば、任意の2接尾辞の最長共通接頭辞（LCE）を $O(1)$ で求められる。複数文字列の一般化Suffix Tree（Generalized Suffix Tree）に拡張すると、最長共通部分文字列問題（LCS）も扱える。
- 次回予告: Li Chao Tree on Segment Tree（区間ごとに独立した直線集合を管理する二重データ構造）