Trong phần này, chúng ta sẽ xem cách so sánh hai chuỗi bằng cách sử dụng thuật toán Wagner và Fisher. Sử dụng thuật toán này, chúng tôi có thể tìm thấy cần có bao nhiêu thay đổi tối thiểu để phù hợp với các chuỗi đó.
Đây là một cách tiếp cận lập trình động. Ở đây chúng tôi đo khoảng cách Levenshtein từ hai chuỗi.
Input: Two strings “Support” & “Suppose” Output: Minimum number of required changes: 2
Thuật toán
Wagnwe_Fisher (str1, str2)
Đầu vào :Hai chuỗi str1 và str2
Đầu ra :Số lượng thay đổi tối thiểu
l1 := length of str1, and l2 = length of str2
define a matrix d of order (l1 * l2)
fill first row of d with numbers from 0 to l1 – 1, and fill first column with numbers from 0 to l2- 1
for j in range 1 to l1, do
for i in range 1 to l2, do
if str1[i - 1] = str2[j - 1], then
tracker := 1
else
tracker := 0
temp := minimum of d[i – 1, j] + 1 and d[i, j-1] + 1
d[i, j] = minimum of temp and (d[i – 1, j - 1]+ tracker)
done
done
return d[l2, l1] Mã mẫu
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int d[100][100];
int min(int a, int b) {
return (a < b) ? a : b;
}
int main() {
int i,j,str1_len,str2_len,temp,tracker;
string str1 = "Support";
string str2 = "Suppose";
str1_len = str1.length();
str2_len = str2.length();
for(i = 0; i <= str1_len;i++)
d[0][i] = i;
for(j = 0;j <= str2_len;j++)
d[j][0] = j;
for (j = 1;j <= str1_len; j++) {
for(i = 1;i <= str2_len;i++) {
if(str1[i-1] == str2[j-1]) {
tracker = 0;
} else {
tracker = 1;
}
temp = min((d[i-1][j]+1),(d[i][j-1]+1));
d[i][j] = min(temp,(d[i-1][j-1]+tracker));
}
}
cout << "The Levinstein distance " << d[str2_len][str1_len];
} Đầu ra:
The Levinstein distance 2