levenshtein.cpp

/**
This snippet is a c++ version of the c# code from http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm
*/
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

double LD(string sRow,string sCol){
    int RowLen=sRow.size();
    int ColLen=sCol.size();
    int RowIdx,ColIdx;
    char Row_i,Col_j;
    int cost;
    if(max(RowLen,ColLen)>1000000){
        return -1;
    }
    if(RowLen==0){
        return ColLen;
    }
    if(ColLen==0){
        return RowLen;
    }

    int *v0=new int[RowLen+1];
    int *v1=new int[RowLen+1];
    int *vTmp;

    v0[0]=0;
    for(RowIdx=1;RowIdx<=RowLen;RowIdx++){
        v0[RowIdx]=RowIdx;
    }

    for(ColIdx=1;ColIdx<=ColLen;ColIdx++){
        v1[0]=ColIdx;

        Col_j=sCol[ColIdx-1];

        for(RowIdx=1;RowIdx<=RowLen;RowIdx++){
            Row_i=sRow[RowIdx-1];

            if(Row_i==Col_j){
                cost=0;
            }
            else{
                cost=1;
            }

            int m_min = v0[RowIdx] + 1;
            int b = v1[RowIdx - 1] + 1;
            int c = v0[RowIdx - 1] + cost;

            if (b < m_min)
            {
                m_min = b;
            }
            if (c < m_min)
            {
                m_min = c;
            }

            v1[RowIdx] = m_min;
        }
        vTmp=v0;
        v0=v1;
        v1=vTmp;
    }
    return ((double(v0[RowLen]))/max(RowLen,ColLen));
}

int main(int argc,char**argv){
    string a(argv[1]),b(argv[2]);
    cout<<LD(a,b)<<endl;

}