Silviu Bogan: [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 <fstream>
#include <string>
#include <stack>
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<string> 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;
}