ABC 377 G — Edit to Match

考察

過去文字列 T を S_k に変える最小操作数は |S_k|+|T|-2·lcp(S_k,T) である。各 prefix p について、p を接頭辞にもつ過去文字列の最小長だけ分かれば全 T の最小を取れる。

採用する候補: 過去文字列を trie に挿入し、各 node にその prefix をもつ文字列の最小長を保持して、S_k の root-to-leaf path 上で式を最小化する。

必要な候補は S_k の各 prefix に対応する O(|S_k|) 個へ集約され、全長和に比例する時間で query と挿入ができる。

棄却する候補: 新しい文字列ごとに全過去文字列との LCP を直接比較する。

文字列数と総長が2×10^5でも、類似した長い文字列が多いと比較総量が二乗になる。

削除して LCP まで戻り、残りを追加する編集だけなので距離式は長さと LCP だけで決まる。

固定 prefix 長 i の候補では |T| が最小の過去文字列だけ残せば、他は同じ LCP で必ず劣る。

trie root を空文字列長0で初期化する。S_k を辿りながら node の minLen を使い |S_k|+minLen-2i を評価し、出力後に path 上の minLen を |S_k| で chmin する。

典型の発動条件

Trie 上の prefix DP

発動条件: 文字列間コストが共通 prefix 長と相手の要約値で決まるとき。

各 prefix node に過去候補の最小長を集約する。

問題固有の要素

編集列を考える代わりに、最適な折返し地点が二文字列の LCP であることを式にする。

別の問題へ持ち帰る視点: 同じ prefix を共有する候補は、将来の query に必要な min 長だけを残せる。

正当性

末尾削除追加だけの最短編集は共通prefixまで戻る距離|S|+|T|−2LCP。固定prefix深さiでは最短の過去Tだけ残せば他Tより候補が悪化しない。全prefix候補を走査するため実際の最良LCPも含まれる。自己挿入前に評価し空列候補をrootへ入れれば全許可過去列との最小値を得る。

実装上の注意

  • 空文字列を過去候補として root に長さ0で入れる。答えを計算してから S_k 自身を挿入し、同時刻の自己利用を防ぐ。

復習の核

  • 距離式 |S|+|T|-2·lcp を先に導き、固定 LCP なら T のどの情報だけが必要かを問い直す。

計算量と制約

時間

O(L)、L=Σ|S_i|。trie上の最小長を更新する。

空間

O(L)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\le N\le 2\times 10^5; Each S_i is a string of length at least 1 consisting of lowercase English letters.; \displaystyle \sum_{i=1}^N |S_i|\le 2\times 10^5

出典

分類・前提・執筆情報

掲載状態: 収録済み

Edit to Match の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Trieで共有接頭辞を索引化する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: Trieによる共有接頭辞の索引

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

      学習の位置

      体系上の位置: Trieで共有接頭辞を索引化する

      • 文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。

      この解説で扱わないこと:

      • failure linkやZ値で接頭辞と接尾辞の一致状態を更新する文字列照合。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題