// SPDX-License-Identifier: WTFPL
// reference: https://en.wikipedia.org/wiki/Levenshtein_distance

#include <stdio.h>
#include <string.h>
#include "lev.h"

static int minimum(int a, int b, int c)
{
	int r;

	r = (a < b) ? a : b;
	r = (r < c) ? r : c;

	return r;
}

int LevenshteinDistance(const char *s, const char *t)
{
	// for all i and j, d[i,j] will hold the Levensthein distance between
	// the first i characters of s and the first j characters of t
	int m = strlen(s), n = strlen(t);
	int d[m + 1][n + 1];
	int i, j, substitutionCost;

	memset(d, 0, sizeof(d));

	// source prefixes can be transformed into empty string by
	// dropping all characters
	for (i = 1; i <= m; i++)
		d[i][0] = i;

	// target prefixes can be reached from empty source prefix
	// by inserting every character
	for (j = 1; j <= n; j++)
		d[0][j] = j;

	for (j = 1; j <= n; j++) {
		for (i = 1; i <= m; i++) {
			if (s[i - 1] == t[j - 1])
				substitutionCost = 0;
			else
				substitutionCost = 1;

			d[i][j] = minimum(d[i - 1][j] + 1,	// deletion
					  d[i][j - 1] + 1,	// insertion
					  d[i - 1][j - 1] +	// substitution
					  substitutionCost);
		}
	}

	return d[m][n];
}