File indexing completed on 2024-05-12 05:41:01
0001 #ifndef LEV_DISTANCE_H 0002 #define LEV_DISTANCE_H 0003 0004 /** 0005 * Levenshtein Distance 0006 * 0007 * Code snippet taken from https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance 0008 * 0009 * Licensed under CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0/) 0010 * 0011 * UNLESS OTHERWISE MUTUALLY AGREED TO BY THE PARTIES IN WRITING, LICENSOR OFFERS THE WORK AS-IS 0012 * AND MAKES NO REPRESENTATIONS OR WARRANTIES OF ANY KIND CONCERNING THE WORK, EXPRESS, IMPLIED, 0013 * STATUTORY OR OTHERWISE, INCLUDING, WITHOUT LIMITATION, WARRANTIES OF TITLE, MERCHANTIBILITY, 0014 * FITNESS FOR A PARTICULAR PURPOSE, NONINFRINGEMENT, OR THE ABSENCE OF LATENT OR OTHER DEFECTS 0015 * ACCURACY, OR THE PRESENCE OF ABSENCE OF ERRORS, WHETHER OR NOT DISCOVERABLE. SOME JURISDICTIONS 0016 * DO NOT ALLOW THE EXCLUSION OF IMPLIED WARRANTIES, SO SUCH EXCLUSION MAY NOT APPLY TO YOU. 0017 * EXCEPT TO THE EXTENT REQUIRED BY APPLICABLE LAW, IN NO EVENT WILL LICENSOR BE LIABLE TO YOU ON 0018 * ANY LEGAL THEORY FOR ANY SPECIAL, INCIDENTAL, CONSEQUENTIAL, PUNITIVE OR EXEMPLARY DAMAGES ARISING 0019 * OUT OF THIS LICENSE OR THE USE OF THE WORK, EVEN IF LICENSOR HAS BEEN ADVISED OF THE POSSIBILITY 0020 * OF SUCH DAMAGES. 0021 **/ 0022 0023 #include <algorithm> 0024 #include <numeric> 0025 #include <string> 0026 0027 int levenshtein_distance(const std::string &s1, const std::string &s2) 0028 { 0029 // To change the type this function manipulates and returns, change 0030 // the return type and the types of the two variables below. 0031 int s1len = s1.size(); 0032 int s2len = s2.size(); 0033 0034 auto column_start = (decltype(s1len))1; 0035 0036 auto *column = new decltype(s1len)[s1len + 1]; 0037 std::iota(column + column_start - 1, column + s1len + 1, column_start - 1); 0038 0039 for (auto x = column_start; x <= s2len; x++) { 0040 column[0] = x; 0041 auto last_diagonal = x - column_start; 0042 for (auto y = column_start; y <= s1len; y++) { 0043 auto old_diagonal = column[y]; 0044 auto possibilities = {column[y] + 1, column[y - 1] + 1, last_diagonal + (s1[y - 1] == s2[x - 1] ? 0 : 1)}; 0045 column[y] = std::min(possibilities); 0046 last_diagonal = old_diagonal; 0047 } 0048 } 0049 auto result = column[s1len]; 0050 delete[] column; 0051 return result; 0052 } 0053 0054 #endif