| 1 |
#ifndef LEV_DISTANCE_H |
| 2 |
#define LEV_DISTANCE_H |
| 3 |
|
| 4 |
/** |
| 5 |
* Levenshtein Distance |
| 6 |
* |
| 7 |
* Code snippet taken from https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance |
| 8 |
* |
| 9 |
* Licensed under CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0/) |
| 10 |
* |
| 11 |
* UNLESS OTHERWISE MUTUALLY AGREED TO BY THE PARTIES IN WRITING, LICENSOR OFFERS THE WORK AS-IS |
| 12 |
* AND MAKES NO REPRESENTATIONS OR WARRANTIES OF ANY KIND CONCERNING THE WORK, EXPRESS, IMPLIED, |
| 13 |
* STATUTORY OR OTHERWISE, INCLUDING, WITHOUT LIMITATION, WARRANTIES OF TITLE, MERCHANTIBILITY, |
| 14 |
* FITNESS FOR A PARTICULAR PURPOSE, NONINFRINGEMENT, OR THE ABSENCE OF LATENT OR OTHER DEFECTS |
| 15 |
* ACCURACY, OR THE PRESENCE OF ABSENCE OF ERRORS, WHETHER OR NOT DISCOVERABLE. SOME JURISDICTIONS |
| 16 |
* DO NOT ALLOW THE EXCLUSION OF IMPLIED WARRANTIES, SO SUCH EXCLUSION MAY NOT APPLY TO YOU. |
| 17 |
* EXCEPT TO THE EXTENT REQUIRED BY APPLICABLE LAW, IN NO EVENT WILL LICENSOR BE LIABLE TO YOU ON |
| 18 |
* ANY LEGAL THEORY FOR ANY SPECIAL, INCIDENTAL, CONSEQUENTIAL, PUNITIVE OR EXEMPLARY DAMAGES ARISING |
| 19 |
* OUT OF THIS LICENSE OR THE USE OF THE WORK, EVEN IF LICENSOR HAS BEEN ADVISED OF THE POSSIBILITY |
| 20 |
* OF SUCH DAMAGES. |
| 21 |
**/ |
| 22 |
|
| 23 |
#include <algorithm> |
| 24 |
#include <numeric> |
| 25 |
#include <string> |
| 26 |
|
| 27 |
inline int levenshtein_distance(const std::string &s1, const std::string &s2) |
| 28 |
{ |
| 29 |
// To change the type this function manipulates and returns, change |
| 30 |
// the return type and the types of the two variables below. |
| 31 |
int s1len = s1.size(); |
| 32 |
int s2len = s2.size(); |
| 33 |
|
| 34 |
auto column_start = (decltype(s1len))1; |
| 35 |
|
| 36 |
auto *column = new decltype(s1len)[s1len + 1]; |
| 37 |
std::iota(column + column_start - 1, column + s1len + 1, column_start - 1); |
| 38 |
|
| 39 |
for (auto x = column_start; x <= s2len; x++) { |
| 40 |
column[0] = x; |
| 41 |
auto last_diagonal = x - column_start; |
| 42 |
for (auto y = column_start; y <= s1len; y++) { |
| 43 |
auto old_diagonal = column[y]; |
| 44 |
auto possibilities = {column[y] + 1, column[y - 1] + 1, last_diagonal + (s1[y - 1] == s2[x - 1] ? 0 : 1)}; |
| 45 |
column[y] = std::min(possibilities); |
| 46 |
last_diagonal = old_diagonal; |
| 47 |
} |
| 48 |
} |
| 49 |
auto result = column[s1len]; |
| 50 |
delete[] column; |
| 51 |
return result; |
| 52 |
} |
| 53 |
|
| 54 |
#endif |