1 
2 #include "levenshtein.h"
3 #include <numeric>
4 #include <algorithm>
5 
levenshtein_distance(const std::string & s1,const std::string & s2)6 int 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