/*
 * 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;
}