数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用瓦格纳和费舍尔算法实现在线字符串匹配的 C++ 程序
在這一章節，我們將瞭解如何使用瓦格納和費舍爾算法比較兩個字串。透過這個算法，我們可以找出使這些字串相匹配所需的最小變更次數。
這是一個動態規劃方法。在此，我們測量兩個字串的李文斯坦距離。
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
更新於： 2019 年 7 月 30 日
335 次檢視
广告