[C++, algoritmică] Distanța Levenshtein cu reconstrucția pașilor de editare

Enunțul problemei:

Se dau 2 șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Asupra șirului A putem face trei operații: 1. inserăm, 2. ștergem, 3. înlocuim un caracter. Se cere determinarea numărului minim de operații necesare transformării șirului de caractere A în șirul de caractere B.

Ca inspirație, cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Programul de mai jos, scurtat și modificat, obține 30 de puncte pe infoarena.ro (la 3 teste obține 10 puncte la fiecare, la restul eroarea „Killed by signal 11(SIGSEGV).”, și nu din cauza utilizării de prea multă memorie).

Fișierul de intrare

Lungimile celor 2 șiruri de caractere vor fi determinate automat.

lev.in:
kitten
sitting

Fișierul de ieșire

Conține matricea creată prin programare dinamică, D, apoi numărul minim de pași de editare necesari, apoi pe fiecare rând câte un pas de editare sub forma „Inlocuire X cu Y”, „Inserare X” sau „Stergere X”, unde X si Y sunt caractere ale alfabetului englez.

lev.out:
1 2 3 4 5 6 7
2 1 2 3 4 5 6
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 2 3
3
Inlocuire k cu s
Inlocuire e cu i
Inserare g

Codul sursă

Source.cpp:
#include
#include
#include
using namespace std;

const int maxn = 101;

int min(int a, int b)
{
    return a < b ? a : b;
}

void levenshtein(const string &A, const string &B,
    int D[maxn][maxn], ofstream &out)
{
    for (int i = 0; i <= A.length(); ++i)
        D[i][0] = i;
    for (int j = 0; j <= B.length(); ++j)
        D[0][j] = j;
    for (int i = 1; i <= A.length(); ++i)
    {
        for (int j = 1; j <= B.length(); ++j)
        {
            if (A[i – 1] == B[j – 1])
                D[i][j] = D[i – 1][j – 1];
            else
                D[i][j] = 1 + min(
                    min(D[i][j – 1],
                        D[i – 1][j]),
                        D[i – 1][j – 1]
                );
            out << D[i][j] << ' ';
        }
        out << endl;
    }

    out << D[A.length()][B.length()] << endl;
}

void reconst(const string &A, const string &B,
    int D[maxn][maxn], ofstream &out)
{
    stack st;

    int i = A.length(), j = B.length();
    while (true)
    {
        string o;
        if (i – 1 < 0 && j – 1 < 0)
        {
            // inceputurile sirurilor
            // coincid
            break;
        }
        else if (i – 1 < 0)
        {
            o = „Inserare „;
            o += B[j – 1];
            st.push(o);
            break;
        }
        else if (j – 1 < 0)
        {
            o = „Stergere „;
            o += A[i – 1];
            st.push(o);
            break;
        }
        else
        {
            if (A[i – 1] == B[j – 1])
            {
                i = i – 1;
                j = j – 1;
                // caractere identice
            }
            else
            {
                if (D[i][j] – 1 == D[i][j – 1])
                {
                    j = j – 1;
                    o = „Inserare „;
                    o += B[j];
                }
                else if (D[i][j] – 1 == D[i – 1][j])
                {
                    i = i – 1;
                    o = „Stergere „;
                    o += B[j];
                }
                else // if (D[i][j] – 1 == D[i – 1][j – 1])
                {
                    i = i – 1;
                    j = j – 1;

                    o = „Inlocuire „;
                    o += A[i];
                    o += ” cu „;
                    o += B[j];
                }
                st.push(o);
            }

            if (i < 0 || j < 0) break;
        }
    }

    while (!st.empty())
    {
        out << st.top() << endl;
        st.pop();
    }
}

int main()
{
    string A, B;
    int D[maxn][maxn];

    ifstream in(„lev.in”);
    in >> A >> B;
    in.close();

    ofstream out(„lev.out”);
    levenshtein(A, B, D, out);
    reconst(A, B, D, out);
    out.close();

    return 0;

Capturi de ecran

Fișier de intrare

 Fișier de ieșire

 Codul sursă

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: