資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 程式實現萊文斯坦距離計算演算法
兩個字串之間的萊文斯坦距離表示將一個字串轉換成另一個字串所需的最小編輯次數，編輯操作包括插入、刪除或替換單個字元。
**例如：**cat 和 mat 之間的萊文斯坦距離為 1 -
cat mat(substitution of ‘c’ with ‘m’)
下面是一個 C++ 程式，用於實現萊文斯坦距離計算演算法。
演算法
Begin Take the strings as input 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];
//take the strings as input
char s1[] = "tutorials";
char s2[] = "point";
//stores the lenght of strings s1 and 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<<"The Levinstein distance is:"<<dist[l2][l1];
return 0;
}輸出
The Levinstein distance is:8
更新於： 30-Jul-2019
3K+ 瀏覽
廣告