#ifndef EDITDISTANCE_H
#define EDITDISTANCE_H

#include <algorithm>
#include <array>
#include <cstdlib>
#include <string_view>
#include <vector>

#include <kblib/fakestd.h>

inline std::size_t edit_distance(std::string_view s, std::string_view t) {
	using uint_t = std::size_t;

	const auto inf = s.size() + t.size();
	std::array<uint_t, 256> DA{};
	std::vector<uint_t> dd((s.size() + 2) * (t.size() + 2));
	auto d = [&](uint_t i, uint_t j) -> decltype(auto) {
		return dd[i * (t.size() + 2) + j];
	};

	d(0u, 0u) = inf;
	for (uint_t i = 0; i < s.size() + 1; i++) {
		d(i + 1, 1) = i;
		d(i + 1, 0) = inf;
	}
	for (uint_t j = 0; j < t.size() + 1; j++) {
		d(1, j + 1) = j;
		d(0, j + 1) = inf;
	}

	for (uint_t i = 1; i < s.size() + 1; i++) {
		uint_t DB = 0;
		for (uint_t j = 1; j < t.size() + 1; j++) {
			auto i1 = DA[kblib::to_unsigned(t[j - 1])];
			auto j1 = DB;
			uint_t cost = ((s[i - 1] == t[j - 1]) ? 0 : 1);

			if (cost == 0) {
				DB = j;
			}
			d(i + 1, j + 1) =
			    std::min({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[kblib::to_unsigned(s[i - 1])] = i;
	}
	return d(s.size() + 1, t.size() + 1);
}

#endif // EDITDISTANCE_H