C ++程序实现Levenshtein距离计算算法
两个字符串之间的Levenshtein距离是指使用编辑操作将一个字符串转换为另一个字符串所需的最少编辑次数。插入，删除或替换单个字符。
例如： 猫和垫子之间的Levenshtein距离为1-
cat mat(substitution of ‘c’ with ‘m’)
这是一个实现Levenshtein距离计算算法的C++程序。
演算法
Begin
将字符串作为输入 and also find their length.
For i = 0 to l1
dist[0][i] = i
For j = 0 to l2
dist[j][0] = j
For j=1 to l1
For i=1 to l2
if(s1[i-1] == s2[j-1])
track= 0
else
track = 1
done
t = MIN((dist[i-1][j]+1),(dist[i][j-1]+1))
dist[i][j] = MIN(t,(dist[i-1][j-1]+track))
Done
Done
Print the Levinstein distance: dist[l2][l1]
End示例
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define MIN(x,y) ((x) < (y) ? (x) : (y)) //calculate minimum between two values
int main() {
int i,j,l1,l2,t,track;
int dist[50][50];
//将字符串作为输入
char s1[] = "tutorials";
char s2[] = "point";
//存储字符串s1和s2的长度
l1 = strlen(s1);
l2= strlen(s2);
for(i=0;i<=l1;i++) {
dist[0][i] = i;
}
for(j=0;j<=l2;j++) {
dist[j][0] = j;
}
for (j=1;j<=l1;j++) {
for(i=1;i<=l2;i++) {
if(s1[i-1] == s2[j-1]) {
track= 0;
} else {
track = 1;
}
t = MIN((dist[i-1][j]+1),(dist[i][j-1]+1));
dist[i][j] = MIN(t,(dist[i-1][j-1]+track));
}
}
cout<<"列文斯坦距离是："<<dist[l2][l1];
return 0;
}输出结果
列文斯坦距离是：8
热门推荐
10 诗词送行祝福语大全简短
11 新房开工吉日祝福语简短
12 50多岁生日简短祝福语
13 安徽疫情祝福语简短英语
14 农民朋友发财祝福语简短
15 对生活祝福语简短精辟
16 搬家词简短祝福语朋友
17 女神结婚快乐祝福语简短
18 文学短句祝福语大全简短