以下の記事のおまけです。 rian.hatenablog.jp そういえば編集距離 (復元なし) 時間 O(|S||T|/w) 空間 O(|S|+|T|) を書いたのを思い出した やっぱりあれと似た方法でできるのか https://t.co/BYr5gBV616— SSRS (@SSRS_cp) 2024年7月14日 おまけなので前回以…

最長共通部分列 (Longest Common Subsequence; LCS) を時間計算量 $\Theta(|S| |T| / w)$、空間計算量 $\Theta(|S| + |T|)$ で復元までします（$w$ はワードサイズ）。 韓国語の記事はいくつか見つかるんですが日本語の記事は見つからないので韓国高度典型な…