1#include <mem/alloc.h>
2#include <stdint.h>
3#include <string.h>
4
5#define MIN(a, b) ((a) < (b) ? (a) : (b))
6
7int64_t levenshtein_distance(const char *s1, const char *s2) {
8 int64_t len1 = strlen(str: s1);
9 int64_t len2 = strlen(str: s2);
10
11 int64_t *prev = kmalloc((len2 + 1) * sizeof(int64_t));
12 int64_t *curr = kmalloc((len2 + 1) * sizeof(int64_t));
13 if (!prev || !curr)
14 return -1;
15
16 for (int64_t j = 0; j <= len2; j++)
17 prev[j] = j;
18
19 for (int64_t i = 1; i <= len1; i++) {
20 curr[0] = i;
21 for (int64_t j = 1; j <= len2; j++) {
22 int64_t cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
23 curr[j] =
24 MIN(MIN(curr[j - 1] + 1, prev[j] + 1), prev[j - 1] + cost);
25 }
26 int64_t *tmp = prev;
27 prev = curr;
28 curr = tmp;
29 }
30
31 int64_t result = prev[len2];
32 kfree(prev);
33 kfree(curr);
34 return result;
35}
36