Levenstein distance

levenstein.cpp

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

namespace {
using Iter = std::string::const_iterator;

double add_cost() { return 1; }
double delete_cost() { return 1; }
double change_cost() { return 1.5; }

double levenstein_distance(const std::string& a, const std::string& b) {
    size_t height = a.length() + 1;
    size_t width = b.length() + 1;
    std::vector<std::vector<double>> mat(height);
    for (auto& row : mat) {
        row.resize(width);
    }
    for (size_t i = 0; i < height; ++i) {
        mat[i][0] = i;
    }
    for (size_t i = 0; i < width; ++i) {
        mat[0][i] = i;
    }
    for (size_t i = 1; i < height; ++i) {
        for (size_t j = 1; j < width; ++j) {
            double cost = a[i - 1] == b[j - 1] ? 0 : change_cost();
            mat[i][j] = std::min(mat[i - 1][j] + delete_cost(),
                                 std::min(mat[i][j - 1] + add_cost(), mat[i - 1][j - 1] + cost));
        }
    }
    return mat[a.length()][b.length()];
}

double distance(const Iter& beg_a, const Iter& end_a, const Iter& beg_b, const Iter& end_b) {
    static std::map<std::pair<Iter, Iter>, double> memo;
    auto k = std::pair<Iter, Iter>(beg_a, beg_b);
    if (memo.count(k) >= 1) {
        return memo[k];
    }

    double result;
    if (beg_a == end_a && beg_b == end_b) {
        result = 0;
    } else if (beg_a == end_a) {
        result = (end_b - beg_b) * add_cost();
    } else if (beg_b == end_b) {
        result = (end_a - beg_a) * delete_cost();
    } else if (*beg_a == *beg_b) {
        result = distance(beg_a + 1, end_a, beg_b + 1, end_b);
    } else {
        result = std::min(add_cost() + distance(beg_a, end_a, beg_b + 1, end_b),
                          std::min(delete_cost() + distance(beg_a + 1, end_a, beg_b, end_b),
                                   change_cost() + distance(beg_a + 1, end_a, beg_b + 1, end_b)));
    }
    memo[k] = result;
    return result;
}
}
int main(int argc, char* argv[]) {
    if (argc != 3) {
        std::cerr << "usage: distance [string1] [string2]" << std::endl;
        return 1;
    }
    std::string a = argv[1];
    std::string b = argv[2];
    std::cout << distance(a.cbegin(), a.cend(), b.cbegin(), b.cend()) << '\n'
              << levenstein_distance(a, b) << std::endl;
    return 0;
}