ABC 257 G — Prefix Concatenation

考察

Tの位置iから切り出せる断片長はSとの最長共通接頭辞L_i以下の全てであり、一つの長さが使えればそれより短いSの接頭辞も全て使える。

採用する候補: Z値と到達可能接頭辞の区間frontier DP

各開始位置iから到達可能な終端が連続区間[i+1,i+L_i]になるため、同じ使用回数で届く最遠端を走査して次のfrontierを線形に広げられる。

棄却する候補: 各位置で最長一致を必ず一断片として選ぶ貪欲法

最長断片を取ると次の境界が合わず、より短い接頭辞で区切れば完成できる場合がある。

棄却する候補: 全ての断片長へDP遷移

L_i個の終端を各位置から列挙すると最悪二次時間になる。

Z-algorithmをS+区切り文字+Tへ適用すれば、全開始位置のL_iを合計線形時間で求められる。

p個以下の断片で到達できる接頭辞長は区間をなし、その全開始位置からのi+L_iの最大がp+1個で届く最遠端になる。

S、未使用文字、Tを連結してZ値から各T位置のL_iを得る。到達済み位置を左から一度ずつ走査し、現在の断片数で使える開始位置のmax(i+L_i)を次frontierとして更新する。frontierが伸びなければ-1、|T|へ達した段階数を答える。

典型の発動条件

Z-algorithm

発動条件: 一つのパターンSと文字列Tの全接尾辞との最長共通接頭辞が必要になる。

連結文字列のZ値を各開始位置の使用可能最大断片長にする。

区間到達のfrontier BFS

発動条件: 一遷移で現在位置から連続した終端区間へ進める。

同じ手数で到達可能な全開始位置をまとめて走査し、次層の最遠端だけを保持する。

問題固有の要素

辞書がSの全接頭辞なので、一致長L_iは単一の辺でなく終端の連続区間を表し、最短分割DPを区間frontierへ圧縮できる。

別の問題へ持ち帰る視点: 可変長遷移が[次の最小位置,最大位置]を全て覆うなら、個別遷移ではなくBFS層の最遠到達点を更新する。

正当性

Z値から開始iに置けるSの接頭辞長L_iが得られ、遷移先は全ての終端[i+1,i+L_i]になる。k断片以下で到達する位置は0からfrontier_kまでの連続区間で、次のfrontierはその範囲の開始点のi+L_iの最大。新たに開いた開始点だけ一度ずつ走査すれば全BFS層を線形に処理できる。frontierが伸びなければ到達不能、初めて|T|を覆う層が最小断片数。現在位置の最長一致を即座に確定する貪欲法とは異なる。

実装上の注意

  • 区切り文字はS,Tに現れないものを選び、L_iを|S|とTの残長で上限化する。各開始位置を高々一回走査し、次frontier≤現在frontierなら不可能とする。

復習の核

  • 二次DPとの比較に加え、最長断片貪欲が失敗するS=aba,T=ababa、先頭不一致、同一文字列、短い接頭辞を多数使う場合を確認する。

計算量と制約

時間

O(|S|+|T|)。

空間

O(|S|+|T|)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq |S| \leq 5\times 10^5; 1 \leq |T| \leq 5\times 10^5; S and T are strings consisting of lowercase English letters.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Prefix Concatenation の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Z algorithmによるprefix matching

主題
  • Z algorithmによるprefix matching: 既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: Z algorithmによるprefix matching

    補助タグ: 状態グラフのモデリングと探索

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: Z algorithmによるprefix matching

    • 既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。

    先に読む単元:

    • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題