前一陣子在博客園搜到有介紹這個好的算法（一個快速、高效的Levenshtein算法實現），今天想起來就把它寫了一下。

#include<iostream> #include<string> #include<vector> #include<conio.h> #include<istream>int min3(int a,int b,int c){if(a < b){return a < c?a:c;}else{return b < c?b:c;} } int main() {std::string str1,str2;std::vector<int> v1;std::vector<int> v2;//輸入要比較的兩個字符串std::cout<<"input a string:";getline(std::cin,str1);std::cout<<"input another string:";getline(std::cin,str2);//交換使str1是短的字符串if(str1.length() > str2.length()){std::string temp = str1;str1 = str2;str2 = temp;}//內外循環次數int outTimes = str1.length();int innerTimes = str2.length();//初始化v1，v2for(int i = 0;i <= innerTimes; ++ i){v1.push_back(i);v2.push_back(0);}for(int i = 0;i < outTimes; ++ i){v2.at(0) = i + 1;for(int j = 0;j < innerTimes; ++ j){//如果不相等，編輯代價為1//找出v1[j+1],v1[j],v2[2]中最小的數，按情況賦給v2[j+1]if(str1.at(i) != str2.at(j)){v2.at(j + 1) = min3(v1.at(j + 1),v1.at(j),v2.at(j)) + 1;}//相等則編輯代價為0else if(str1.at(i) == str2.at(j)){v2.at(j + 1) = min3(v1.at(j + 1),v1.at(j),v2.at(j));}}//v1，v2逐次向右平移 v1.assign(v2.begin(),v2.end());}//v2的最后一個元素即為距離int changTimes = v2.at(innerTimes);std::cout<<"\nthe distance of two string is "<<changTimes;getch(); }

轉載于:https://www.cnblogs.com/hellophone/archive/2012/10/24/2737760.html

總結

以上是生活随笔為你收集整理的用C++写的 Levenshtein 算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。