levenshpp/levenshtein.hpp

#pragma once

#include <utility>
#include <queue>

template <class T, typename SIZE=unsigned int>
int levenshtein(const T &a, const T &b, const SIZE aSize, const SIZE bSize)
{
    int **items = new int*[aSize +1]();

    for (SIZE i =0; i <= aSize; i++)
    {
        items[i] = new int[bSize +1]();
        items[i][0] = i;
        if (i == 0)
            for (SIZE j =1; j <= bSize; j++)
                items[i][j] = j;
        else
            for (SIZE j =1; j <= bSize; j++)
                items[i][j] = std::min(std::min(
                            items[i][j -1] +1,
                            items[i -1][j] +1),
                            (items[i -1][j -1] + (a[i -1] == b[j -1] ? 0 : 1)));
    }
    const int levenshtein = items[aSize][bSize];
    for (SIZE i =0; i < aSize +1; i++)
        delete[] items[i];
    delete[] items;
    return levenshtein;
}