ლევენშტეინის მანძილი

ლევენშტეინის მანძილი ან ცვლილებათა მანძილი — ოპერაციების მინიმალური რაოდენობა ერთი სტრიქონის მეორე სტრიქონამდე შეცვლისთვის. ოპერაციები შემდეგია: სიმბოლოს ჩამატება (მაგ. "აბგ" >"აბგა"), სიმბოლოს წაშლა (მაგ. "აბგ"->"აგ") და სიმბოლოს შეცვლა (მაგ. "აბგ"->"ადგ").

მაგალითად, ცვლილებათა მანძილი "თეორემა" -> "თეორია" არის 2, ცვლილებები შემდეგია: "თეორემა" -> "თეორმა" (წაშლა), შემდეგ "თეორმა"->"თეორია" (ჩანაცვლება).

დავუშვათ, მოცემულია $n$ სიგრძის სტრიქონი $x$ და $m$ სიგრძის სტრიქონი $y$ და გვინდა გამოვთვალოთ ცვლილებათა მანძილი ამ სტრიქონებს შორის. ამის ამოსახსნელად, შემოვიღოთ ფუნქცია $distance(a,b)$, რომელიც გვიბრუნებს ცვლილებათა მანძილს პრეფიქსების, $x[0...a$] და $y[0...b]$, შორის. ამ ფუნქციის გამოყენებით ლევენშტეინის მანძილი $x$ და $y$ სტრიქონებს შორის არის $distance(n-1,m-1)$. ფუნქცია გამოიყურება შემდეგნაირად

$distance(a,b)=min(distance(a,b-1)+1,distance(a-1,b)+1,distance(a-1,b-1)+cost(a,b)).$

აქ $cost(a,b)=0$, თუ $x[a]=y[b]$, თუ არა, $cost(a,b)=1$. $x$ სტრიქონის შეცვლისთვის ფორმულა განიმარტება შემდეგნაირად:

• $distance(a,b-1)$: $x$ სტრიქონის ბოლოში სიმბოლოს ჩამატება
• $distance(a-1,b)$: $x$ სტრიქონის ბოლო სიმბოლოს წაშლა
• $distance(a-1,b-1)$: $x$ სტრიქონის ბოლო სიმბოლოს დამთხვევა ან შეცვლა.

იმპლემენტაცია C++-ზე

#include <bits/stdc++.h>

using namespace::std;

int dp[1001][1001];
int main() {
    string a, b;
    cin >> a >> b;
    const int n = a.length(), m = b.length();

    for (int i = 0; i <= n; i++)
        dp[i][0] = i;

    for (int i = 0; i <= m; i++)
        dp[0][i] = i;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
           if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];

           //                    წაშლა        ჩამატება        ჩანაცვლება
           else dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1;
        }
    }
    cout << dp[n][m];
    return 0;
}

ლიტერატურა

• Antti Laaksonen, Competitive Programmer's Handbook, 2018. p74.