fork(2) download
copy 
  1. #include <string>
  2. #include <algorithm>
  3. #include <numeric>
  4. #include <functional>
  5. using namespace std;
  6.  
  7.  
  8. int levenshtein_distance(const std::string &s1, const std::string &s2)
  9. {
  10. 	int s1len = s1.size();
  11. 	int s2len = s2.size();
  12.  
  13. 	auto column_start = (decltype(s1len))1;
  14.  
  15. 	auto column = new decltype(s1len)[s1len + 1];
  16. 	iota(column + column_start, column + s1len + 1, column_start);
  17.  
  18. 	for (auto x = column_start; x <= s2len; x++) {
  19. 		column[0] = x;
  20. 		auto last_diagonal = x - column_start;
  21. 		for (auto y = column_start; y <= s1len; y++) {
  22. 			auto old_diagonal = column[y];
  23. 			auto possibilities = {
  24. 				column[y] + 1,
  25. 				column[y - 1] + 1,
  26. 				last_diagonal + (s1[y - 1] == s2[x - 1] ? 0 : 1)
  27. 			};
  28. 			column[y] = std::min(possibilities);
  29. 			last_diagonal = old_diagonal;
  30. 		}
  31. 	}
  32. 	auto result = column[s1len];
  33. 	delete[] column;
  34. 	return result;
  35. }
  36.  
  37. #define H_G "\x01"
  38. #define H_N "\x02"
  39. #define H_D "\x03"
  40. #define H_R "\x04"
  41. #define H_M "\x05"
  42. #define H_B "\x06"
  43. #define H_S "\x07"
  44. #define H_0 "\x08"
  45. #define H_J "\x09"
  46. #define H_C "\x0A"
  47. #define H_K "\x0B"
  48. #define H_T "\x0C"
  49. #define H_P "\x0D"
  50. #define H_H "\x0E"
  51.  
  52. #define H_A "\x10"
  53. #define H_AE "\x11"
  54. #define H_YA "\x12"
  55. #define H_EO "\x13"
  56. #define H_E "\x14"
  57. #define H_YEO "\x15"
  58. #define H_O "\x16"
  59. #define H_YO "\x17"
  60. #define H_U "\x18"
  61. #define H_YU "\x19"
  62. #define H_EU "\x1A"
  63. #define H_I "\x1B"
  64.  
  65. #define H_SH "\x1F"
  66.  
  67. string disassembleKo2(const string& s)
  68. {
  69. 	static const char* mtbl1[] = { H_G, H_G H_SH,
  70. 		H_N, H_D, H_D H_SH, H_R, H_M, H_B,
  71. 		H_B H_SH, H_S, H_S H_SH, H_0, H_J, H_J H_SH,
  72. 		H_C, H_K, H_T, H_P, H_H };
  73.  
  74. 	static const char* mtbl2[] = { H_A, H_AE, H_YA, H_AE H_SH,
  75. 		H_EO, H_E, H_YEO, H_E H_SH,
  76. 		H_O, H_O H_A, H_O H_AE, H_O H_I, H_YO,
  77. 		H_U, H_U H_EO, H_U H_E, H_U H_I, H_YU,
  78. 		H_EU, H_EU H_I, H_I };
  79.  
  80. 	static const char* mtbl3[] = { "", H_G, H_G H_SH, H_G H_S,
  81. 		H_N, H_N H_J, H_N H_H, H_D,
  82. 		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,
  83. 		H_M, H_B, H_B H_S, H_S, H_S H_SH, H_0, H_J,
  84. 		H_C, H_K, H_T, H_P, H_H };
  85.  
  86. 	static const char* mtbl4[] = {H_G, H_G H_SH, H_G H_S,
  87. 		H_N, H_N H_J, H_N H_H, H_D, H_D H_SH,
  88. 		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,
  89. 		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,
  90. 		H_C, H_K, H_T, H_P, H_H };
  91.  
  92. 	string ret;
  93. 	for (size_t i = 0; i < s.size(); i++)
  94. 	{
  95. 		if (s[i] & 0xE0 != 0xE0)
  96. 		{
  97. 			ret.push_back(s[i]);
  98. 			continue;
  99. 		}
  100. 		if (i + 2 >= s.size()) break;
  101.  
  102. 		int chr = (s[i] & 0x0F) << 12;
  103. 		chr |= (s[i + 1] & 0x3F) << 6;
  104. 		chr |= (s[i + 2] & 0x3F);
  105.  
  106. 		if (chr >= 0xAC00 && chr < 0xD7B0)
  107. 		{
  108. 			chr -= 0xAC00;
  109. 			int p1 = chr / (28 * 21),
  110. 				p2 = (chr % (28 * 21)) / 28,
  111. 				p3 = chr % 28;
  112. 			ret.append(mtbl1[p1]);
  113. 			ret.append(mtbl2[p2]);
  114. 			if(p3) ret.append(mtbl3[p3]);
  115. 		}
  116. 		else if (chr >= 0x1100 && chr < 0x1200)
  117. 		{
  118. 			if (chr < 0x1100 + 19) ret.append(mtbl1[chr - 0x1100]);
  119. 			else if (chr < 0x1161);
  120. 			else if (chr < 0x1161 + 21) ret.append(mtbl2[chr - 0x1161]);
  121. 			else if (chr <= 0x11A8);
  122. 			else if (chr < 0x11A8 + 28) ret.append(mtbl2[chr - 0x11A8]);
  123. 		}
  124. 		else if (chr >= 0x3131 && chr < 0x319F)
  125. 		{
  126. 			if (chr < 0x3131 + 30) ret.append(mtbl4[chr - 0x3131]);
  127. 			else if (chr < 0x314F + 21) ret.append(mtbl2[chr - 0x314F]);
  128. 		}
  129. 		else
  130. 		{
  131. 			ret.insert(ret.end(), &s[i], &s[i] + 3);
  132. 		}
  133. 		i += 2;
  134. 	}
  135. 	return ret;
  136. }
  137.  
  138. int levenshtein_distance_map(const std::string & s1, const std::string & s2, const function<string(const string&)>& mapFunc)
  139. {
  140. 	string r1 = mapFunc(s1), r2 = mapFunc(s2);
  141. 	return levenshtein_distance(r1, r2);
  142. }
  143.  
  144. void test(const char* a, const char* b)
  145. {
  146. 	printf("%s - %s : %d (%d)\n", a, b,
  147. 		levenshtein_distance_map(a, b, disassembleKo2), 
  148. 		levenshtein_distance(a, b));
  149. }
  150.  
  151. int main() 
  152. {
  153. 	test("없어", "ㅇ벗어");
  154. 	test("빼고", "뺴고");
  155. 	test("기다료", "기다려");
  156. 	test("소고기", "소거기");
  157. 	test("애이", "에이");
  158. 	test("잇어", "있어");
  159. 	test("그랬는데", "글샌ㄴ데");
  160. 	return 0;
  161. }
  162.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
없어 - ㅇ벗어 : 2 (6)
빼고 - 뺴고 : 1 (2)
기다료 - 기다려 : 1 (2)
소고기 - 소거기 : 1 (2)
애이 - 에이 : 1 (2)
잇어 - 있어 : 1 (1)
그랬는데 - 글샌ㄴ데 : 3 (8)
https://ideone.com/b0ppIN
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!