Distanța de editare Levenshtein în C++

Distanța de editare Levenshtein este numărul minim de inserări, ștergeri și înlocuiri de caractere necesare pentru a transforma un text în altul. Fiecare operație costă 1. Pentru cat și cut, este suficientă înlocuirea lui a cu u, deci distanța este 1.

Starea descrie două prefixe

Folosim programare dinamică: rezolvăm probleme mai mici și păstrăm rezultatele pentru a le reutiliza. Notăm cu dp[i][j] costul minim de a transforma primele i caractere din a în primele j caractere din b. Un prefix este partea de la început a unui text.

Citim două linii de cel mult 100 de litere mici a..z fiecare. Acceptăm și linii goale. Afișăm distanța. Nu tratăm diacritice sau caractere reprezentate prin mai mulți octeți; codul lucrează pe alfabetul declarat.

Pentru a transforma un prefix de i caractere în textul gol, ștergem toate cele i caractere: dp[i][0]=i. Pentru a construi j caractere pornind de la gol, facem j inserări: dp[0][j]=j. Aceste margini nu sunt simple valori de conveniență, ci soluții ale unor probleme reale.

Ultima operație are trei posibilități

Putem șterge ultimul caracter din primul prefix, insera ultimul caracter cerut de al doilea sau potrivi cele două caractere finale. Dacă ele sunt egale, potrivirea costă zero; altfel, înlocuirea costă unu. Alegem minimul celor trei costuri.

Pentru cat și cut, primul și ultimul caracter coincid. Înlocuim numai a cu u, deci distanța de editare este 1.Mărește schema ↗

Varianta cu char[]

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
    char a[101],b[101]; cin.getline(a,101); cin.getline(b,101);
    int n=static_cast<int>(strlen(a)),m=static_cast<int>(strlen(b));
    int dp[101][101]={};
    for(int i=0;i<=n;++i) dp[i][0]=i;
    for(int j=0;j<=m;++j) dp[0][j]=j;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
        int cost=a[i-1]==b[j-1]?0:1;
        dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost});
    }
    cout << dp[n][m] << '\n';
}

Varianta echivalentă cu std::string

Păstrăm aceleași limite și exemple. Șirul clasic rezervă spațiu inclusiv pentru terminatorul nul; obiectul string își gestionează memoria. Indicii caracterelor utile pornesc de la zero în ambele variante.

#include <string>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    string a,b; getline(cin,a); getline(cin,b);
    int n=static_cast<int>(a.size()),m=static_cast<int>(b.size());
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    for(int i=0;i<=n;++i) dp[i][0]=i;
    for(int j=0;j<=m;++j) dp[0][j]=j;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
        int cost=a[i-1]==b[j-1]?0:1;
        dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost});
    }
    cout << dp[n][m] << '\n';
}

Lungimea prefixului diferă de indicele literei

Starea dp[i][j] privește i și j caractere, dar ultimele lor caractere au indicii i-1 și j-1. De aceea buclele de tranziție încep la 1. Linia și coloana zero reprezintă texte goale, nu caractere de pe poziția zero.

Tablourile char rezervă 101 celule, inclusiv terminatorul nul. Matricea clasică rezervă 101×101 stări; varianta vector construiește exact (n+1)×(m+1). Ambele folosesc aceleași operații și aceleași rezultate.

Timpul și memoria sunt O((n+1)(m+1)). Pentru texte nevide, acest cost se scrie uzual O(n·m). Metoda calculează numărul minim, dar codul nu reconstruiește lista operațiilor; pentru aceasta trebuie urmărită și alegerea care a produs fiecare stare.

Exersează

kitten devine sitting în trei operații: înlocuiești k cu s, e cu i și adaugi g. Distanța dintre textul gol și abc este 3, iar dintre două texte identice este 0. Verifică simetria rezultatului la inversarea celor două intrări.

Continuă cu programarea dinamică, subșirul comun maxim și reprezentarea textului.

Întrebări frecvente

Ce este distanța Levenshtein?

Numărul minim de inserări, ștergeri și înlocuiri de caractere necesare pentru transformarea unui text în altul, fiecare cu cost 1. Între cat și cut, distanța este 1.

Ce reprezintă starea dp[i][j] la distanța de editare?

Costul minim de a transforma primele i caractere ale primului text în primele j ale celui de-al doilea. Tranzițiile corespund inserării, ștergerii și potrivirii sau înlocuirii ultimului caracter.

Care este distanța dintre un text și șirul gol?

Lungimea textului: trebuie șterse toate caracterele sau, în sens invers, inserate toate. Aceste valori inițializează marginile tabelului de programare dinamică.