[問題案] Edit Distance

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker

https://judge.yosupo.jp/

Apache License 2.0

497 stars 116 forks source link

Open SSRS-cp opened 1 year ago

SSRS-cp commented 1 year ago

問題名: Edit Distance (Levenshtein Distance のほうがよいか？要検討) 想定解: Myers' bit-parallel algorithm (計算量 $O(|S||T|/w)$) 資料

文字列 $S, T$ が与えられる。$S$ と $T$ の編集距離を求めよ。

$1 \leq |S|, |T| \leq 100000$

S
T

答え

yosupo06 commented 1 year ago

実際の操作列を復元させた方がいいかもです(GCJかなにかで復元が必要な問題を見た記憶が)

Bit並列で復元ができるのか未調査です

maspypy commented 3 weeks ago