C++ levenshtein distance

[codesafer]

template< typename T >

const T min( const T a, const T b )

{

    if( a < b ) return a;

    return b;

}

template< typename T, typename ...TS >

const T min( const T a, const TS ...args )

{

    return min( a, min( args... ) );

}

template<typename T>

int levenshtein_distance( const T* series1, const T* series2,

    const int count1, const int count2 )

{

    int count = count2 + 1;

    int* map = (int*)_alloca( sizeof(int) * count * 2 );

    int* p0 = map;

    int* p1 = map + count;

    for( int y = 0; y < count; ++y ) p0[y] = y;

    for( int y = 0; y < count1; ++y )

    {

        p1[0] = y + 1;

        T s = series1[y];

        for( int x = 0; x < count2; ++x )

            p1[x + 1] = min( p1[x] + 1, p0[x + 1] + 1, p0[x] + ( s != series2[x] ) );

        int* t = p0;

        p0 = p1;

        p1 = t;

    }

    return p0[count2];

}

template<typename T>

int levenshtein_distance( const T* series1, const T* series2 )

{

    return levenshtein_distance( series1, series2, strlen( series1 ), strlen( series2 ) );

}

[codesafer]

예전에 누가 퀴즈 내서 풀어본 것.

[codesafer]

찜찜하던 코드 revision 완료 !