問題とコンテキスト
ストリーム s[0..n) が与えられ、1文字ずつ末尾に追加されます。追加が行われるたびに、相異なる回文部分文字列の数、各回文の出現回数、および現在のプレフィックスの最長回文接尾辞を維持します。追加のたびにすべての部分文字列を再列挙するのではなく、オンラインで処理する必要があります。
eertree（回文木）は、相異なる回文ごとに1つのノードを保持します。エッジは両端に同じ文字を追加することを表し、接尾辞リンク（suffix link）は最長の真の回文接尾辞（proper palindromic suffix）を指します。優れた回答では、2つの番兵根、拡張可能な接尾辞の見つけ方、および各位置で最大1つのノードしか作成されない理由を説明します。
面接官が見ているポイント
- 長さ
-1と長さ0の根を正しく区別できているか。 last、最長回文接尾辞、および接尾辞リンクを理解しているか。- 追加時に拡張可能なノードを見つけ、トランジションを作成できるか。
- 末尾追加モデルにおける
O(n)のノード数、時間、空間の計算量境界を把握しているか。 - 繰り返し文字、空文字列、アルファベットの表現、および出現回数の伝播を適切に処理できるか。
- 回文分割やスライディングウィンドウのバリアントへ構造を拡張できるか。
最初に確認すべき明確化のための質問
- 入力は一括の文字列ですか、それとも右側への末尾追加のみのストリームですか？左側からの削除は必要ですか？
- 出現回数は終了位置ごとにカウントしますか、それとも最終的な総出現頻度としてカウントしますか？
- アルファベットは英小文字、Unicode、あるいは任意の整数トークンですか？
- 出力には回文のテキスト、ノードID、または長さとカウントのみのいずれを含める必要がありますか？
- オンラインでの最小分割数が必要ですか、それとも相異なる回文の集合を維持するだけで十分ですか？
30秒の回答フレームワーク
長さ -1 と長さ 0 の2つの根を使用します。各通常ノードには、回文の長さ、最長の真の回文接尾辞への接尾辞リンク、および文字トランジションを格納します。last は現在のプレフィックスの最長回文接尾辞です。文字 c が到着した際、両側を c で挟むことができるまで接尾辞リンクをたどります。既存のトランジションを再利用するか新しく作成し、リンクチェーンから新しいノードの接尾辞リンクを計算します。1つの位置で追加される相異なるノードは最大1つであるため、構築は O(n) となり、接尾辞リンクの逆順で出現回数を伝播させることで最終的な出現頻度が得られます。
ステップごとの詳細解説
1. 2つの根とノードのフィールド
奇数長の根は長さ -1 を持ち、任意の文字で拡張可能な番兵として機能します。偶数長の根は長さ 0 を持ち、空の回文を表します。通常ノードは len、link、next、occ、およびオプションで終了位置を格納します。last は偶数長の根から開始します。
2. 拡張可能な接尾辞の探索
位置 pos に c を追加した後、last から開始し、そのノードの回文の直前にある文字が c と等しいかどうかをテストします。等しくない場合は、v = link[v] を設定して続行します。最初に一致したものが、拡張可能な最長回文接尾辞です。
while s[pos - 1 - len[v]] != c:
v = link[v]奇数長の根のチェックで負のインデックスを読み込まないようにするため、アルファベット外の番兵を先頭に付加するのが一般的な実装です。
3. トランジションとノードの追加
next[v][c] が既に存在する場合、それが新しい last となり、その occ が増加します。存在しない場合は、長さ len[v] + 2 のノードを作成し、トランジションを割り当てます。長さ1のノードは偶数長の根に直接リンクします。それより長いノードの場合は、c に対する対応するトランジションが見つかるまで link[v] をたどります。
4. ノードが1つしか追加されない理由
1回の末尾追加によって新しく作成されるすべての回文は、新しい文字で終わる必要があります。そのような回文のうち、最長のものだけが新しいノードになります。それより短い回文接尾辞は、すでに接尾辞リンクのチェーン上に存在しています。したがって、各位置で作成される相異なるノードは最大1つであり、全体のノード数は最大でも n + 2 に保たれます。
5. 出現回数の伝播
オンライン処理中、各位置で終了する最長回文接尾辞に対して occ をインクリメントします。入力終了後、ノードを長い方から短い方へと処理し、occ[v] を occ[link[v]] に加算します。これにより、すべての出現がその回文接尾辞すべてに転送されます。相異なる回文の数のみが必要な場合は、通常ノードの数を返します。
6. 回文分割への拡張
最小回文分割数を求めるには、last 接尾辞リンクチェーンをたどって各位置で終了する回文を列挙し、dp[pos] = min(dp[pos - len[v]] + 1) を更新します。単純にチェーンを走査すると O(n^2) になる可能性があります。シリーズリンクを使用すると、長さの差が等しい連続するノードをグループ化できますが、この最適化は制約を確認した後にのみ選択すべきです。
7. 境界条件、アルファベット、および計算量
空の入力には2つの根のみが存在します。繰り返し文字はトランジションを再利用するため、重複したノードを作成してはなりません。小さいアルファベットの場合は O(n * alphabet) のトランジションストレージを持つ固定配列を使用できます。大きいアルファベットの場合はハッシュマップまたは順序付きマップが必要となり、期待計算量 O(n) または O(n log σ) の挙動になります。右側への末尾追加のみのモデルでは、期待定数時間のハッシュトランジションを用いた場合、構築は O(n)、空間計算量は O(n) にトランジションストレージを加えたものになります。
質の高い模範解答
まず、右側追加のみであること、アルファベットの種類、および出現回数の定義を確認します。構造体には長さ -1 と 0 の2つの根があります。通常ノードは相異なる回文を表し、last は現在のプレフィックスの最長回文接尾辞です。追加される各 c について、c で挟むことができる最長ノードまで接尾辞リンクをたどります。そのトランジションが存在しない場合、長さ len + 2 のノードを作成します。長さ1のノードは偶数長の根にリンクし、より長いノードは親の接尾辞リンクチェーンをたどってリンク先を見つけます。各位置で作成されるノードは最大1つであるため、構築は線形時間です。各 last を記録し、長いノードからそのリンク先へカウントを伝播させることで、総出現頻度が得られます。左側からの削除、任意の位置への挿入、または大規模なアルファベットを扱う場合は、構造と計算量を再検討する必要があります。
よくある間違い
- 単一の空の根を使用する → 奇数長と偶数長の境界処理が複雑になる →
-1と0の両方の根を維持する。 - 追加のたびに根から再探索する → オンラインの線形性が失われる →
lastから接尾辞リンクをたどる。 lastを全体の最長回文として扱う → これは最長「回文接尾辞」にすぎない。- 新しいノードをその親にリンクする → リンクは最長の「真の回文接尾辞」を指す必要がある。
- 追加のたびにすべての回文をインクリメントする → 重複カウントが発生する → 終了ノードを記録し、リンクの逆順で伝播させる。
- 任意のUnicodeに対して小さな固定配列を適用する → 衝突やオーバーフローが発生する → エンコーディングとマッピングを明示的に定義する。
フォローアップ質問と回答
どのような場合に代わりにManacher法を選択しますか？
各中心における最長半径のみが必要な静的文字列に対しては、Manacher法が適しています。eertreeはすべての相異なる回文を表現し、オンラインでの末尾追加、ノードレベルのカウント、接尾辞リンククエリを自然にサポートします。
現在の最長回文のテキストを返すにはどうすればよいですか？
各ノードに終了位置を保存します。その位置と len のペアにより、保持されている入力内のスライスが特定されます。入力を破棄するストリームの場合は、リングバッファまたは外部ストレージが必要です。
なぜ出現回数を逆順で伝播させるのですか？
より長い回文のすべての出現は、そのリンクパス上の各回文接尾辞の出現でもあります。長いノードから先に処理することで、親に追加される前に各子ノードの寄与が完全に計算されていることが保証されます。
この構造は左側からの削除に対応できますか？
通常のeertreeは右側への追加のみをサポートします。スライディングウィンドウには両端対応のバリアント（double-ended variant）または再構築/ブロッキングが必要となり、選択はウィンドウサイズと削除レートに依存します。
ハッシュマップによるトランジションでは何が変わりますか？
ハッシュマップを使用すると、期待トランジション探索時間は O(1)、期待構築時間は O(n) になります。最悪計算量の挙動はハッシュの実装に依存します。順序付きマップは O(log σ) の係数を伴う決定論的な境界を提供します。