Debian Codegraph @

src/checks/manuallevel/levenshteindistance.h

raw
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