#ifndef EDITDISTANCE_H
#define EDITDISTANCE_H

#include <array>
#include <cstdlib>
#include <string_view>

inline int dldist2(char const* s, char const* t, int n, int m);

inline int editDistance(std::string_view s1, std::string_view s2) {
	return dldist2(s1.data(), s2.data(), s1.length(), s2.length());
	// Eigen::ArrayXXi dd(s1.length(), s2.length());
}

#define d(i, j) dd[(i) * (m + 2) + (j)]
#define min(x, y) ((x) < (y) ? (x) : (y))
#define min3(a, b, c) ((a) < (b) ? min((a), (c)) : min((b), (c)))
#define min4(a, b, c, d) ((a) < (b) ? min3((a), (c), (d)) : min3((b), (c), (d)))
#undef INFINITY

// void dprint(int* dd, int n,int m){
// int i,j;
// for (i=0; i < n+2;i++){
// for (j=0;j < m+2; j++){
// printf("%02d ",d(i,j));
// }
// printf("\n");
// }
// printf("\n");
// }

inline int dldist2(char const* s, char const* t, int n, int m) {
	int* dd;
	int i, j, cost, i1, j1;
	int INFINITY = n + m;
	std::array<int, 256> DA;

	DA.fill(0);

	if (!(dd = (int*)malloc((n + 2) * (m + 2) * sizeof(int)))) {
		return -1;
	}

	d(0, 0) = INFINITY;
	for (i = 0; i < n + 1; i++) {
		d(i + 1, 1) = i;
		d(i + 1, 0) = INFINITY;
	}
	for (j = 0; j < m + 1; j++) {
		d(1, j + 1) = j;
		d(0, j + 1) = INFINITY;
	}
	// dprint(dd,n,m);

	for (i = 1; i < n + 1; i++) {
		int DB = 0;
		for (j = 1; j < m + 1; j++) {
			i1 = DA[t[j - 1]];
			j1 = DB;
			cost = ((s[i - 1] == t[j - 1]) ? 0 : 1);
			if (cost == 0)
				DB = j;
			d(i + 1, j + 1) =
			    min4(d(i, j) + cost, d(i + 1, j) + 1, d(i, j + 1) + 1,
			         d(i1, j1) + (i - i1 - 1) + 1 + (j - j1 - 1));
		}
		DA[s[i - 1]] = i;
		// dprint(dd,n,m);
	}
	cost = d(n + 1, m + 1);
	free(dd);
	return cost;
}

#undef d
#undef min
#undef min3
#undef min4

#endif // EDITDISTANCE_H