考察
通常の編集距離DPは|S||T|だが、dp[i][j]≥|i-j|である。判定閾値K≤20を超える|i-j|のcellは最終的なYes経路へ参加できない。挿入・削除・置換の各遷移は距離を減らさないので、対角線から幅Kのbandだけ正確に計算すれば判定結果を保てる。長さ差がKを超えるなら編集距離も必ずK超なので即Noにできる。band外をINF=K+1として扱えば、境界から誤って安い遷移が入ることを防げる。
採用する候補: Levenshtein DPを|i-j|≤Kの帯状領域だけで計算する
各rowの有効cellがO(K)個になり、標準遷移をそのままO((|S|+|T|)K)へ削減できる。
棄却する候補: 全(|S|+1)(|T|+1) cellの編集距離DP
文字列長が5×10^5で二次時間・メモリとも不可能である。
長さ差がKを超えるなら編集距離も必ずK超なので即Noにできる。
まず長さ差を判定する。rolling arrayでiを進め、jを[max(0,i-K),min(|T|,i+K)]だけ走査し、削除・挿入・一致/置換の標準三遷移をK+1でcapする。最後がK以下か答える。
典型の発動条件
banded edit-distance DP
発動条件: 編集距離が小さいかだけを、小さい閾値Kで判定するとき。
下界|i-j|で不要cellを除き対角帯だけ計算する。
閾値DPのcap
発動条件: K以下かだけが必要で値が単調非減少するとき。
K+1以上を同じINFへ丸めて状態を安全に制限する。
問題固有の要素
入力長は巨大でもYesとなり得るalignmentは主対角からK以上ずれられず、制約KがDPの幾何的な幅を決める。
別の問題へ持ち帰る視点: 二次元DPで目的値に簡単な下界があるなら、閾値判定では下界が閾値を超える領域を切り落とす。
正当性
prefix長差|i−j|は挿入削除の最低回数なのでKを超えるcellは最終距離K以内pathに現れない。帯内の標準三遷移は全許容編集列を網羅する。K+1でcapしても≤K判定は変わらない。
実装上の注意
- rowごとにj範囲がずれるためrolling index対応を明示し、空prefixの初期値をband内だけ設定する。|S|-|T|の絶対値を先に確認する。
復習の核
- 空prefix境界、長さ差がKちょうど/K+1、全一致、挿入と削除が交互に必要な短列をfull DPとrandom比較する。
計算量と制約
時間
文字列長n,m、許容編集K。帯内 O((n+m)(K+1))。
空間
rolling band O(K+1)、入力O(n+m)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.; K is an integer satisfying \color{red}{1 \le K \le 20}.
出典