C ++程序，用于实现在线字符串匹配的Wagner和Fisher算法
在本节中，我们将看到如何使用Wagner和Fisher算法比较两个字符串。使用此算法，我们可以找到匹配这些字符串所需的最小变化量。
这是一种动态编程方法。在这里，我们从两个弦测量Levenshtein距离。
Input: Two strings “Support” & “Suppose” Output: Minimum number of required changes: 2
算法
Wagnwe_Fisher(str1,str2)
输入：两个字符串str1和str2
输出：最小更改次数
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]范例程式码
#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];
}输出：
The Levinstein distance 2