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

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
Jump to navigation Jump to search

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

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

დავუშვათ, მოცემულია სიგრძის სტრიქონი და სიგრძის სტრიქონი და გვინდა გამოვთვალოთ ცვლილებათა მანძილი ამ სტრიქონებს შორის. ამის ამოსახსნელად, შემოვიღოთ ფუნქცია , რომელიც გვიბრუნებს ცვლილებათა მანძილს პრეფიქსების, ] და , შორის. ამ ფუნქციის გამოყენებით ლევენშტეინის მანძილი და სტრიქონებს შორის არის . ფუნქცია გამოიყურება შემდეგნაირად

აქ , თუ , თუ არა, . სტრიქონის შეცვლისთვის ფორმულა განიმარტება შემდეგნაირად:

  • : სტრიქონის ბოლოში სიმბოლოს ჩამატება
  • : სტრიქონის ბოლო სიმბოლოს წაშლა
  • : სტრიქონის ბოლო სიმბოლოს დამთხვევა ან შეცვლა.

იმპლემენტაცია C++-ზე[რედაქტირება | წყაროს რედაქტირება]

#include <iostream>
#include <string>

using namespace::std;

int dp[1001][1001];
int main() {
    string a, b;
    cin >> a >> b;
    int n = a.length();
    int 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++) {
            //წაშლა
            dp[i][j] = dp[i - 1][j] + 1;
            //ჩამატება
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
            //ჩანაცვლება
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            //არც ერთი
            if (a[i - 1] == b[j - 1])
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
        }
    }
    cout << dp[n][m];
    return 0;
}


ლიტერატურა[რედაქტირება | წყაროს რედაქტირება]

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