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回のまま正しい値です。