ლევენშტეინის მანძილი: განსხვავება გადახედვებს შორის
[შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
No edit summary |
|||
ხაზი 21: | ხაზი 21: | ||
==იმპლემენტაცია C++-ზე== |
==იმპლემენტაცია C++-ზე== |
||
<source lang="cpp"> |
<source lang="cpp"> |
||
#include < |
#include <bits/stdc++.h> |
||
#include <string> |
|||
using namespace::std; |
using namespace::std; |
||
ხაზი 41: | ხაზი 40: | ||
for (int j = 1; j <= m; j++) { |
for (int j = 1; j <= m; j++) { |
||
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1]; |
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 |
else dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1; |
||
} |
} |
||
} |
} |
||
ხაზი 49: | ხაზი 48: | ||
return 0; |
return 0; |
||
} |
} |
||
</source> |
</source> |
||
== ლიტერატურა == |
== ლიტერატურა == |
უკანასკნელი რედაქცია 21:31, 7 სექტემბერი 2020-ის მდგომარეობით
ლევენშტეინის მანძილი ან ცვლილებათა მანძილი — ოპერაციების მინიმალური რაოდენობა ერთი სტრიქონის მეორე სტრიქონამდე შეცვლისთვის. ოპერაციები შემდეგია: სიმბოლოს ჩამატება (მაგ. "აბგ" >"აბგა"), სიმბოლოს წაშლა (მაგ. "აბგ"->"აგ") და სიმბოლოს შეცვლა (მაგ. "აბგ"->"ადგ").
მაგალითად, ცვლილებათა მანძილი "თეორემა" -> "თეორია" არის 2, ცვლილებები შემდეგია: "თეორემა" -> "თეორმა" (წაშლა), შემდეგ "თეორმა"->"თეორია" (ჩანაცვლება).
დავუშვათ, მოცემულია სიგრძის სტრიქონი და სიგრძის სტრიქონი და გვინდა გამოვთვალოთ ცვლილებათა მანძილი ამ სტრიქონებს შორის. ამის ამოსახსნელად, შემოვიღოთ ფუნქცია , რომელიც გვიბრუნებს ცვლილებათა მანძილს პრეფიქსების, ] და , შორის. ამ ფუნქციის გამოყენებით ლევენშტეინის მანძილი და სტრიქონებს შორის არის . ფუნქცია გამოიყურება შემდეგნაირად
აქ , თუ , თუ არა, . სტრიქონის შეცვლისთვის ფორმულა განიმარტება შემდეგნაირად:
- : სტრიქონის ბოლოში სიმბოლოს ჩამატება
- : სტრიქონის ბოლო სიმბოლოს წაშლა
- : სტრიქონის ბოლო სიმბოლოს დამთხვევა ან შეცვლა.
იმპლემენტაცია 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.