//
//  main.cpp
//  p17-2-levenshtein
//
//  Created by Andreas on 26.03.15.
//  Copyright (c) 2015 Andreas. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;

int levenshtein(string a, string b) {
    vector<vector<int>> lev_mtx(a.size()+1,vector<int>(b.size()+1,0));
    
    for (size_t i=0; i <= a.size(); i++) {
        for (size_t j=0; j <= b.size(); j++) {
            if (i == 0 && j == 0) {
                lev_mtx[i][j] = 0;
            } else if (i == 0) {
                lev_mtx[i][j] = j;
            } else if (j == 0) {
                lev_mtx[i][j] = i;
            } else {
                auto ins = lev_mtx[i-1][j] + 1;
                auto del = lev_mtx[i][j-1] + 1;
                auto rep = lev_mtx[i-1][j-1] + (a[i-1] == b[i-1] ? 0 : 1);
                lev_mtx[i][j] = min(min(ins,del),rep);
            }
        }
    }
    return lev_mtx[a.size()][b.size()];
}

int main(void) {
    string a = "Vier";
    string b = "Vieh";
    /*
      . T i e r
    . 0 1 2 3 4
    T 1 0 1 2 3
    o 2 1 1 2 3
    r 3 2 2 2 2
    */
    
    
    
    cout << "Levenshtein distance between \"" << a << "\" & \"" << b << "\": " << levenshtein(a,b) << "\n";
    
    
    
    return 0;
}