initial commit

Signed-off-by: Chloe M <chloe@faracom.org>

1 files changed, 77 insertions, 0 deletions

diff --git a/levd/levd.c b/levd/levd.c
new file mode 100644
index 0000000..16da6d5
--- /dev/null
+++ b/levd/levd.c
@@ -0,0 +1,77 @@
+/*
+ * Copyright (c) 2026, Chloe M., et al.
+ * Provided under the BSD-3 clause.
+ */
+
+#include <stdio.h>
+#include <string.h>
+
+/*
+ * Compute the levenshtein distance between two strings
+ *
+ * @s1:  First string to compare
+ * @s2:  Second string to compare
+ * @l1:  Length of first string to compare
+ * @l2:  Length of second string to compare
+ */
+static int
+lev_distance(const char *s1, const char *s2, size_t l1, size_t l2)
+{
+    int matrix[l1 + 1][l2 + 1];
+    int i, j, c1, c2;
+    int delete, insert;
+    int subst, min;
+
+    for (i = 0; i <= l1; ++i) {
+        matrix[i][0] = i;
+    }
+
+    for (i = 0; i < l2; ++i) {
+        matrix[0][i] = i;
+    }
+
+    for (i = 1; i <= l1; ++i) {
+        c1 = s1[i - 1];
+        for (j = 1; j <= l2; ++j) {
+            c2 = s2[j - 1];
+            if (c1 == c2) {
+                matrix[i][j] = matrix[i-1][j-1];
+            } else {
+                delete = matrix[i-1][j] + 1;
+                insert = matrix[i][j-1] + 1;
+                subst = matrix[i-1][j-1] + 1;
+                min = delete;
+
+                if (insert < min)
+                    min = insert;
+                if (subst < min)
+                    min = subst;
+
+                matrix[i][j] = min;
+            }
+        }
+    }
+
+    return matrix[l1][l2];
+}
+
+int
+main(int argc, char **argv)
+{
+    char *s1, *s2;
+    size_t l1, l2;
+
+    if (argc < 3) {
+        printf("fatal: expected s1 and s2\n");
+        return -1;
+    }
+
+    s1 = argv[1];
+    s2 = argv[2];
+    
+    l1 = strlen(s1);
+    l2 = strlen(s2);
+
+    printf("%d\n", lev_distance(s1, s2, l1, l2));
+    return 0;
+}