考察
過去文字列 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
出典