前一阵子在博客园搜到有介绍这个好的算法(一个快速、高效的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,v2 for(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; } //相等则编辑代价为0 else 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(); }