levenshtein.cpp

levenshtein.cpp

#define replace_cost(s,t) 1
#define insert_cost(s) 1
#define delete_cost(s) 1

// String mag ook een vector van iets zijn wat te comparen is
int levenshtein(string s, string t)
{
    int sl = s.length();
    int tl = t.length();
    // init DP table
    int d[sl + 1][tl + 1];
    d[0][0] = 0;
    for (int i = 1; i <= sl; i++) {
        d[i][0] = d[i - 1][0] + delete_cost(s[i - 1]);
    }
    for (int j = 1; j <= tl; j++) {
        d[0][j] = d[0][j - 1] + insert_cost(t[i - 1]);
    }
    // fill the complete table
    for (int j = 1; j <= tl; j++) {
        for (int i = 1; i <= sl; i++) {
            if (s[i - 1] == t[j - 1]) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                d[i][j] = min(
                        d[i - 1][j] + delete_cost(s[i - 1]),
                    min(d[i][j - 1] + insert_cost(t[j - 1]),
                        d[i - 1][j - 1] + replace_cost(s[i - 1], t[j - 1])));
            }
        }
    }
    return d[sl][tl];
}