#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;


int levenshtein_distance(const std::string &s1, const std::string &s2)
{
	int s1len = s1.size();
	int s2len = s2.size();

	auto column_start = (decltype(s1len))1;

	auto column = new decltype(s1len)[s1len + 1];
	iota(column + column_start, column + s1len + 1, column_start);

	for (auto x = column_start; x <= s2len; x++) {
		column[0] = x;
		auto last_diagonal = x - column_start;
		for (auto y = column_start; y <= s1len; y++) {
			auto old_diagonal = column[y];
			auto possibilities = {
				column[y] + 1,
				column[y - 1] + 1,
				last_diagonal + (s1[y - 1] == s2[x - 1] ? 0 : 1)
			};
			column[y] = std::min(possibilities);
			last_diagonal = old_diagonal;
		}
	}
	auto result = column[s1len];
	delete[] column;
	return result;
}

#define H_G "\x01"
#define H_N "\x02"
#define H_D "\x03"
#define H_R "\x04"
#define H_M "\x05"
#define H_B "\x06"
#define H_S "\x07"
#define H_0 "\x08"
#define H_J "\x09"
#define H_C "\x0A"
#define H_K "\x0B"
#define H_T "\x0C"
#define H_P "\x0D"
#define H_H "\x0E"

#define H_A "\x10"
#define H_AE "\x11"
#define H_YA "\x12"
#define H_EO "\x13"
#define H_E "\x14"
#define H_YEO "\x15"
#define H_O "\x16"
#define H_YO "\x17"
#define H_U "\x18"
#define H_YU "\x19"
#define H_EU "\x1A"
#define H_I "\x1B"

#define H_SH "\x1F"

string disassembleKo2(const string& s)
{
	static const char* mtbl1[] = { H_G, H_G H_SH,
		H_N, H_D, H_D H_SH, H_R, H_M, H_B,
		H_B H_SH, H_S, H_S H_SH, H_0, H_J, H_J H_SH,
		H_C, H_K, H_T, H_P, H_H };

	static const char* mtbl2[] = { H_A, H_AE, H_YA, H_AE H_SH,
		H_EO, H_E, H_YEO, H_E H_SH,
		H_O, H_O H_A, H_O H_AE, H_O H_I, H_YO,
		H_U, H_U H_EO, H_U H_E, H_U H_I, H_YU,
		H_EU, H_EU H_I, H_I };

	static const char* mtbl3[] = { "", H_G, H_G H_SH, H_G H_S,
		H_N, H_N H_J, H_N H_H, H_D,
		H_R, H_R H_G, H_R H_M, H_R H_B, H_R H_S, H_R H_T, H_R H_P, H_R H_H,
		H_M, H_B, H_B H_S, H_S, H_S H_SH, H_0, H_J,
		H_C, H_K, H_T, H_P, H_H };

	static const char* mtbl4[] = {H_G, H_G H_SH, H_G H_S,
		H_N, H_N H_J, H_N H_H, H_D, H_D H_SH,
		H_R, H_R H_G, H_R H_M, H_R H_B, H_R H_S, H_R H_T, H_R H_P, H_R H_H,
		H_M, H_B, H_B H_SH, H_B H_S, H_S, H_S H_SH, H_0, H_J, H_J H_SH,
		H_C, H_K, H_T, H_P, H_H };

	string ret;
	for (size_t i = 0; i < s.size(); i++)
	{
		if (s[i] & 0xE0 != 0xE0)
		{
			ret.push_back(s[i]);
			continue;
		}
		if (i + 2 >= s.size()) break;

		int chr = (s[i] & 0x0F) << 12;
		chr |= (s[i + 1] & 0x3F) << 6;
		chr |= (s[i + 2] & 0x3F);

		if (chr >= 0xAC00 && chr < 0xD7B0)
		{
			chr -= 0xAC00;
			int p1 = chr / (28 * 21),
				p2 = (chr % (28 * 21)) / 28,
				p3 = chr % 28;
			ret.append(mtbl1[p1]);
			ret.append(mtbl2[p2]);
			if(p3) ret.append(mtbl3[p3]);
		}
		else if (chr >= 0x1100 && chr < 0x1200)
		{
			if (chr < 0x1100 + 19) ret.append(mtbl1[chr - 0x1100]);
			else if (chr < 0x1161);
			else if (chr < 0x1161 + 21) ret.append(mtbl2[chr - 0x1161]);
			else if (chr <= 0x11A8);
			else if (chr < 0x11A8 + 28) ret.append(mtbl2[chr - 0x11A8]);
		}
		else if (chr >= 0x3131 && chr < 0x319F)
		{
			if (chr < 0x3131 + 30) ret.append(mtbl4[chr - 0x3131]);
			else if (chr < 0x314F + 21) ret.append(mtbl2[chr - 0x314F]);
		}
		else
		{
			ret.insert(ret.end(), &s[i], &s[i] + 3);
		}
		i += 2;
	}
	return ret;
}

int levenshtein_distance_map(const std::string & s1, const std::string & s2, const function<string(const string&)>& mapFunc)
{
	string r1 = mapFunc(s1), r2 = mapFunc(s2);
	return levenshtein_distance(r1, r2);
}

void test(const char* a, const char* b)
{
	printf("%s - %s : %d (%d)\n", a, b,
		levenshtein_distance_map(a, b, disassembleKo2), 
		levenshtein_distance(a, b));
}

int main() 
{
	test("없어", "ㅇ벗어");
	test("빼고", "뺴고");
	test("기다료", "기다려");
	test("소고기", "소거기");
	test("애이", "에이");
	test("잇어", "있어");
	test("그랬는데", "글샌ㄴ데");
	return 0;
}