#include <algorithm>
#include <string.h>

int LevenshteinDistance(const char *s, const char *t) {
	int m = strlen(s), n = strlen(t), rowOffset = n+1;
	int *d = new int[(m+1) * (n+1)];

	for (int i=0; i<=m; ++i)
		d[i*rowOffset] = i;
	for (int j=0; j<=n; ++j)
		d[j] = j;

	for (int j=0; j<n; ++j) {
		for (int i=0; i<m; ++i) {
			int cost = (s[i] != t[j]) ? 1 : 0;
			d[(i+1)*rowOffset+j+1] = std::min(std::min(
				d[i*rowOffset+j+1] + 1,		// insertion
				d[(i+1)*rowOffset+j] + 1),	// deletion
				d[i*rowOffset+j] + cost);	// substitution
		}
	}

	int ret = d[m*rowOffset+n];
	delete[] d;
	return ret;
}

int DamerauLevenshteinDistance(const char *s, const char *t) {
	int m = strlen(s), n = strlen(t), rowOffset = n+1;
	int *d = new int[(m+1) * (n+1)];

	for (int i=0; i<=m; ++i)
		d[i*rowOffset] = i;
	for (int j=0; j<=n; ++j)
		d[j] = j;

	for (int j=0; j<n; ++j) {
		for (int i=0; i<m; ++i) {
			int cost = (s[i] != t[j]) ? 1 : 0;
			int &dref = d[(i+1)*rowOffset+j+1];
			dref = std::min(std::min(
				d[i*rowOffset+j+1] + 1,		// insertion
				d[(i+1)*rowOffset+j] + 1),	// deletion
				d[i*rowOffset+j] + cost);	// substitution
			if (i > 0 && j > 0 && s[i] == t[j-1] && s[i-1] == t[j]) {
				dref = std::min(dref,
					d[(i-1)*rowOffset+j-1] + cost);   // transposition
			}
		}
	}

	int ret = d[m*rowOffset+n];
	delete[] d;
	return ret;
}