library-checker-problems icon indicating copy to clipboard operation
library-checker-problems copied to clipboard

Published 20 hours ago • verified publisher icon yosupo06

[問題案] Edit Distance

Open SSRS-cp opened this issue 2 years ago • 3 comments

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

問題

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

制約

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

入力

S
T

出力

答え

SSRS-cp avatar Sep 30 '22 01:09 SSRS-cp

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

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

yosupo06 avatar Oct 03 '22 04:10 yosupo06

資料登場 https://rian.hatenablog.jp/entry/2024/07/14/215634

maspypy avatar Jul 14 '24 13:07 maspypy