編集距離

2022年12月24日

説明

文字列 $S$ と文字列 $T$ との編集距離の遷移の考え方は図の通り。
$s_i = t_j$ のとき $ed(S_i, T_j) = ed(S_{i-1}, T_{j-1})$
$s_i \not= t_j$ のとき $ed(S_i, T_j) = min(ed(S_{i-1}, T_{j-1}, ed(S_{i-1}, T_j), ed(S_i, T_{j-1})) + 1$