Revisions to Edit Distance Between Two Strings

edited tags

Link

edited Dec 21, 2013 at 0:57

200_success

145.7k
22
191
481

Post Unlocked by Adam

occurred Nov 23, 2013 at 1:32

Notice removed Content dispute by Adam

occurred Nov 23, 2013 at 1:32

Post Locked by Jamal

occurred Nov 23, 2013 at 0:58

Notice added Content dispute by Jamal

occurred Nov 23, 2013 at 0:58

Rollback to Revision 6

Source Link

edited Nov 23, 2013 at 0:58

Jamal

35.2k
13
134
238

#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

constinline size_t insert_costmin(size_t =x, 1;
constsize_t y, size_t delete_costz)
{
 = 1;  if (x < y)
const size_t replace_cost = 2;    return x < z ? x : z;
    else
        return y < z ? y : z;
}

size_t edit_distance(const string& A, const string& B)
{
    size_t NA = A.size();
    size_t NB = B.size();

    vector<size_t>vector<vector<size_t>> M0M(NB+1)NA + 1, M1vector<size_t>(NB+1NB + 1));

    for (size_t ba = 0; ba <= NB;NA; ++b++a)
        M0[b]M[a][0] = b * delete_cost;a;

    for (size_t ab = 1;0; ab <= NA;NB; ++a++b)
    {
    M[0][b] = b;

    M1[0]for (size_t a = 1; a *<= insert_cost;
NA; ++a)
        for (size_t b = 1; b <= NB; ++b)
        {
            size_t x = M0[b]M[a-1][b] + insert_cost;1;
            size_t y = M1[bM[a][b-1] + delete_cost;1;
            size_t z = M0[bM[a-1][b-1] + (A[a-1] == B[b-1] ? 0 : replace_cost2);
            M1[b]M[a][b] = min({x,y,z});
        }

       return swapM[A.size(M0,M1);
    }

    return M0[NB];][B.size()];
}

int main()
{
    assert(edit_distance("ISLANDER", "SLANDER") == 1);
    assert(edit_distance("MART", "KARMA") == 5);
    assert(edit_distance("KITTEN", "SITTING") == 5);
    assert(edit_distance("INTENTION", "EXECUTION") == 8);
}

#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const size_t insert_cost = 1;
const size_t delete_cost = 1;
const size_t replace_cost = 2;

size_t edit_distance(const string& A, const string& B)
{
    size_t NA = A.size();
    size_t NB = B.size();

    vector<size_t> M0(NB+1), M1(NB+1);

    for (size_t b = 0; b <= NB; ++b)
        M0[b] = b * delete_cost;

    for (size_t a = 1; a <= NA; ++a)
    {
        M1[0] = a * insert_cost;

        for (size_t b = 1; b <= NB; ++b)
        {
            size_t x = M0[b] + insert_cost;
            size_t y = M1[b-1] + delete_cost;
            size_t z = M0[b-1] + (A[a-1] == B[b-1] ? 0 : replace_cost);
            M1[b] = min({x,y,z});
        }

        swap(M0,M1);
    }

    return M0[NB];
}

int main()
{
    assert(edit_distance("ISLANDER", "SLANDER") == 1);
    assert(edit_distance("MART", "KARMA") == 5);
    assert(edit_distance("KITTEN", "SITTING") == 5);
    assert(edit_distance("INTENTION", "EXECUTION") == 8);
}

#include <cassert>
#include <string>
#include <vector>
using namespace std;

inline size_t min(size_t x, size_t y, size_t z)
{
    if (x < y)
        return x < z ? x : z;
    else
        return y < z ? y : z;
}

size_t edit_distance(const string& A, const string& B)
{
    size_t NA = A.size();
    size_t NB = B.size();

    vector<vector<size_t>> M(NA + 1, vector<size_t>(NB + 1));

    for (size_t a = 0; a <= NA; ++a)
        M[a][0] = a;

    for (size_t b = 0; b <= NB; ++b)
        M[0][b] = b;

    for (size_t a = 1; a <= NA; ++a)
        for (size_t b = 1; b <= NB; ++b)
        {
            size_t x = M[a-1][b] + 1;
            size_t y = M[a][b-1] + 1;
            size_t z = M[a-1][b-1] + (A[a-1] == B[b-1] ? 0 : 2);
            M[a][b] = min(x,y,z);
        }

    return M[A.size()][B.size()];
}

int main()
{
    assert(edit_distance("ISLANDER", "SLANDER") == 1);
    assert(edit_distance("MART", "KARMA") == 5);
    assert(edit_distance("KITTEN", "SITTING") == 5);
    assert(edit_distance("INTENTION", "EXECUTION") == 8);
}

c++ strings c++11

Rollback to Revision 4

Source Link

edited Nov 23, 2013 at 0:31

user1131146 account abandoned

773
1
10
19

#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

inline size_t min(size_t x, size_t y,const size_t z)
{
    if (x < y)
        return x < z ? xinsert_cost := z;1;
const size_t delete_cost = else1;
        return y < zconst ?size_t yreplace_cost := z;
}2;

size_t edit_distance(const string& A, const string& B)
{
    size_t NA = A.size();
    size_t NB = B.size();

    vector<vector<size_t>>vector<size_t> MM0(NA + 1NB+1), vector<size_t>M1(NB + 1)NB+1);

    for (size_t ab = 0; ab <= NA;NB; ++a++b)
        M[a][0]M0[b] = a;b * delete_cost;

    for (size_t ba = 0;1; ba <= NB;NA; ++b++a)
       {
 M[0][b] = b;

    for (size_t aM1[0] = 1; a <= NA;* ++a)insert_cost;

        for (size_t b = 1; b <= NB; ++b)
        {
            size_t x = M[a-1][b]M0[b] + 1;insert_cost;
            size_t y = M[a][bM1[b-1] + 1;delete_cost;
            size_t z = M[a-1][bM0[b-1] + (A[a-1] == B[b-1] ? 0 : 2replace_cost);
            M[a][b]M1[b] = min({x,y,z});
        }

    return M[A.size()][B.size   swap(M0,M1)];;
    }

    return M0[NB];
}

int main()
{
    assert(edit_distance("ISLANDER", "SLANDER") == 1);
    assert(edit_distance("MART", "KARMA") == 5);
    assert(edit_distance("KITTEN", "SITTING") == 5);
    assert(edit_distance("INTENTION", "EXECUTION") == 8);
}

#include <cassert>
#include <string>
#include <vector>
using namespace std;

inline size_t min(size_t x, size_t y, size_t z)
{
    if (x < y)
        return x < z ? x : z;
    else
        return y < z ? y : z;
}

size_t edit_distance(const string& A, const string& B)
{
    size_t NA = A.size();
    size_t NB = B.size();

    vector<vector<size_t>> M(NA + 1, vector<size_t>(NB + 1));

    for (size_t a = 0; a <= NA; ++a)
        M[a][0] = a;

    for (size_t b = 0; b <= NB; ++b)
        M[0][b] = b;

    for (size_t a = 1; a <= NA; ++a)
        for (size_t b = 1; b <= NB; ++b)
        {
            size_t x = M[a-1][b] + 1;
            size_t y = M[a][b-1] + 1;
            size_t z = M[a-1][b-1] + (A[a-1] == B[b-1] ? 0 : 2);
            M[a][b] = min(x,y,z);
        }

    return M[A.size()][B.size()];
}

int main()
{
    assert(edit_distance("ISLANDER", "SLANDER") == 1);
    assert(edit_distance("MART", "KARMA") == 5);
    assert(edit_distance("KITTEN", "SITTING") == 5);
    assert(edit_distance("INTENTION", "EXECUTION") == 8);
}

#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const size_t insert_cost = 1;
const size_t delete_cost = 1;
const size_t replace_cost = 2;

size_t edit_distance(const string& A, const string& B)
{
    size_t NA = A.size();
    size_t NB = B.size();

    vector<size_t> M0(NB+1), M1(NB+1);

    for (size_t b = 0; b <= NB; ++b)
        M0[b] = b * delete_cost;

    for (size_t a = 1; a <= NA; ++a)
    {
        M1[0] = a * insert_cost;

        for (size_t b = 1; b <= NB; ++b)
        {
            size_t x = M0[b] + insert_cost;
            size_t y = M1[b-1] + delete_cost;
            size_t z = M0[b-1] + (A[a-1] == B[b-1] ? 0 : replace_cost);
            M1[b] = min({x,y,z});
        }

        swap(M0,M1);
    }

    return M0[NB];
}

int main()
{
    assert(edit_distance("ISLANDER", "SLANDER") == 1);
    assert(edit_distance("MART", "KARMA") == 5);
    assert(edit_distance("KITTEN", "SITTING") == 5);
    assert(edit_distance("INTENTION", "EXECUTION") == 8);
}

c++ strings c++11

edited tags

Link

edited Nov 22, 2013 at 4:09

200_success

145.7k
22
191
481

Loading

Rollback to Revision 1

Source Link

edited Nov 21, 2013 at 19:20

Jamal

35.2k
13
134
238

Loading

Tweeted twitter.com/#!/StackCodeReview/status/194201406985617408

occurred Apr 22, 2012 at 23:09

added 28 characters in body

Source Link

edited Apr 20, 2012 at 3:26

user1131146 account abandoned

773
1
10
19

Loading

added 217 characters in body

Source Link

edited Apr 19, 2012 at 17:06

user1131146 account abandoned

773
1
10
19

Loading

deleted 12 characters in body

Source Link

edited Mar 18, 2012 at 22:34

user1131146 account abandoned

773
1
10
19

Loading

Source Link

asked Mar 18, 2012 at 21:24

user1131146 account abandoned

773
1
10
19

Loading

Stack Exchange Network

Return to Question