diff options
Diffstat (limited to 'src/string.cpp')
| -rw-r--r-- | src/string.cpp | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/src/string.cpp b/src/string.cpp index 165468965..fcf271d67 100644 --- a/src/string.cpp +++ b/src/string.cpp @@ -762,3 +762,42 @@ i32 unquote_string(gbAllocator a, String *s_, u8 quote=0, bool has_carriage_retu } return 2; } + + +isize levenstein_distance_case_insensitive(String const &a, String const &b) { + isize w = a.len+1; + isize h = b.len+1; + isize *matrix = gb_alloc_array(heap_allocator(), isize, w*h); + for (isize i = 0; i <= a.len; i++) { + matrix[i*w + 0] = i; + } + for (isize i = 0; i <= b.len; i++) { + matrix[0*w + i] = i; + } + + for (isize i = 1; i <= a.len; i++) { + char a_c = gb_char_to_lower(cast(char)a.text[i-1]); + for (isize j = 1; j <= b.len; j++) { + char b_c = gb_char_to_lower(cast(char)b.text[j-1]); + if (a_c == b_c) { + matrix[i*w + j] = matrix[(i-1)*w + j-1]; + } else { + isize remove = matrix[(i-1)*w + j] + 1; + isize insert = matrix[i*w + j-1] + 1; + isize substitute = matrix[(i-1)*w + j-1] + 1; + isize minimum = remove; + if (insert < minimum) { + minimum = insert; + } + if (substitute < minimum) { + minimum = substitute; + } + matrix[i*w + j] = minimum; + } + } + } + + isize res = matrix[a.len*w + b.len]; + gb_free(heap_allocator(), matrix); + return res; +} |