Namaran

Code daily. Without assist.

2026-11-06

typo_distance.cpp

#include <algorithm>
#include <print>
#include <string_view>

int distance(std::string_view a, std::string_view b) {
    int d[16][16] = {};
    for (std::size_t i = 1; i <= a.size(); ++i) {
        for (std::size_t j = 1; j <= b.size(); ++j) {
            int sub = d[i - 1][j - 1] + (a[i - 1] != b[j - 1]);
            d[i][j] = std::min({d[i - 1][j] + 1, d[i][j - 1] + 1, sub});
        }
    }
    return d[a.size()][b.size()];
}

int main() {
    std::println("{}", distance("cat", "concat"));
}

distance は、15文字以下の2つの単語について、1文字の挿入・削除・置き換えを1回と数えて a を b に変える最小の回数を返すつもりの関数です。distance("cat", "concat") を表示すると、いまは 0 が出ます。本来は con の3文字を足す分の 3 です。

Answer

Wrong

int d[16][16] = {};
for (std::size_t i = 1; i <= a.size(); ++i) {

d[i][j] は、a の先頭 i 文字を b の先頭 j 文字に変える最小の回数です。ループは i と j が1以上のところだけを埋め、0行目と0列目は = {} で入れた0のまま残ります。0列目の d[i][0] は a の先頭 i 文字を空文字列に変える回数で、本来は i 文字を消す i 回です。0行目の d[0][j] も同じく、空文字列から b の先頭 j 文字を作る j 回でなければなりません。

端が0だと、どちらかの先頭の文字を何文字でも0回で足したり消したりできることになります。d[0][3] が0なので、concat の con を足す分がただになり、残りの cat どうしは一致して d[3][6] も0になります。distance("abc", "") のように b が空のときは内側のループが一度も回らず、d[3][0] の0がそのまま返ります。

Right

int d[16][16] = {};
for (std::size_t i = 0; i <= a.size(); ++i) {
    d[i][0] = i;
}
for (std::size_t j = 0; j <= b.size(); ++j) {
    d[0][j] = j;
}

表を埋める前に、0列目を d[i][0] = i、0行目を d[0][j] = j にします。どちらも、片方が空文字列のときは、もう一方の文字数だけ削除か挿入をするしかないからです。d[0][3] が3になるので、con を足す3回が数えられ、distance("cat", "concat") は3を返します。d[0][0] だけは、空文字列どうしで0回のまま正しい値です。