1 2 #include "levenshtein.h" 3 #include <numeric> 4 #include <algorithm> 5 levenshtein_distance(const std::string & s1,const std::string & s2)6int levenshtein_distance(const std::string &s1, const std::string &s2) 7 { 8 int s1len = s1.size(); 9 int s2len = s2.size(); 10 11 auto column_start = (decltype(s1len))1; 12 13 auto column = new decltype(s1len)[s1len + 1]; 14 std::iota(column + column_start - 1, column + s1len + 1, column_start - 1); 15 16 for (auto x = column_start; x <= s2len; x++) { 17 column[0] = x; 18 auto last_diagonal = x - column_start; 19 for (auto y = column_start; y <= s1len; y++) { 20 auto old_diagonal = column[y]; 21 auto v1 = column[y] + 1; 22 auto v2 = column[y - 1] + 1; 23 auto v3 = last_diagonal + (s1[y - 1] == s2[x - 1]? 0 : 1); 24 column[y] = v1<v2 ? (v1<v3 ? v1 : v3) : ( v2<v3 ? v2 : v3); 25 last_diagonal = old_diagonal; 26 } 27 } 28 auto result = column[s1len]; 29 delete[] column; 30 return result; 31 } 32