fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Text.RegularExpressions;
  6.  
  7. namespace RegexNegativePatternsForString
  8. {
  9. 	internal class Program
  10. 	{
  11. 		public static void Main()
  12. 		{
  13. 			int maxLengthNGWord = 5;
  14. 			foreach (var nChar in Enumerable.Range(1, maxLengthNGWord))
  15. 			{
  16. 				string ngWord = new string(Enumerable.Range(0, nChar).Select(it => Convert.ToChar('a' + it)).ToArray());
  17. 				string pattern = string.Format("^{0}$", RegexPatternGenerator.GenerateNegativePattern(ngWord));
  18. 				Regex regex = new Regex(pattern);
  19. 				TestNeg(regex, ngWord);
  20. 			}
  21. 		}
  22.  
  23. 		private static void TestNeg(Regex regex, string ngWord)
  24. 		{
  25. 			Console.WriteLine("==================== NG-word: {0} ====================", ngWord);
  26.  
  27. 			var alphabets = Enumerable.Range(0, ngWord.Length + 1).Select(it => Convert.ToChar('a' + it));
  28. 			StringBuilder sb = new StringBuilder();
  29. 			int nCases = 0;
  30.  
  31. 			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets))
  32. 			{
  33. 				sb.Clear();
  34. 				sb.Append(item.Item1);
  35. 				sb.Append(item.Item2);
  36.  
  37. 				string input = sb.ToString();
  38. 				TestNeg(input, regex, ngWord);
  39. 				nCases++;
  40. 			}
  41. 			Console.WriteLine("---------- any 2-length word: {0} cases", nCases);
  42.  
  43. 			nCases = 0;
  44. 			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets))
  45. 			{
  46. 				sb.Clear();
  47. 				sb.Append(item.Item1);
  48. 				sb.Append(item.Item2);
  49. 				sb.Append(item.Item3);
  50.  
  51. 				string input = sb.ToString();
  52. 				TestNeg(input, regex, ngWord);
  53. 				nCases++;
  54. 			}
  55. 			Console.WriteLine("---------- any 3-length word: {0} cases", nCases);
  56.  
  57. 			nCases = 0;
  58. 			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets, alphabets))
  59. 			{
  60. 				sb.Clear();
  61. 				sb.Append(item.Item1);
  62. 				sb.Append(item.Item2);
  63. 				sb.Append(item.Item3);
  64. 				sb.Append(item.Item4);
  65.  
  66. 				string input = sb.ToString();
  67. 				TestNeg(input, regex, ngWord);
  68. 				nCases++;
  69. 			}
  70. 			Console.WriteLine("---------- any 4-length word: {0} cases", nCases);
  71.  
  72. 			nCases = 0;
  73. 			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets, alphabets, alphabets))
  74. 			{
  75. 				sb.Clear();
  76. 				sb.Append(item.Item1);
  77. 				sb.Append(item.Item2);
  78. 				sb.Append(item.Item3);
  79. 				sb.Append(item.Item4);
  80. 				sb.Append(item.Item5);
  81.  
  82. 				string input = sb.ToString();
  83. 				TestNeg(input, regex, ngWord);
  84. 				nCases++;
  85. 			}
  86. 			Console.WriteLine("---------- any 5-length word: {0} cases", nCases);
  87.  
  88. 			nCases = 0;
  89. 			foreach (var item in DirectProductEnumerator.DP(alphabets, alphabets, alphabets, alphabets, alphabets, alphabets))
  90. 			{
  91. 				sb.Clear();
  92. 				sb.Append(item.Item1);
  93. 				sb.Append(item.Item2);
  94. 				sb.Append(item.Item3);
  95. 				sb.Append(item.Item4);
  96. 				sb.Append(item.Item5);
  97. 				sb.Append(item.Item6);
  98.  
  99. 				string input = sb.ToString();
  100. 				TestNeg(input, regex, ngWord);
  101. 				nCases++;
  102. 			}
  103. 			Console.WriteLine("---------- any 6-length word: {0} cases", nCases);
  104. 		}
  105.  
  106. 		private static void TestNeg(string input, Regex regex, string ng)
  107. 		{
  108. 			bool actual = regex.IsMatch(input);
  109. 			bool expected = !input.Contains(ng);
  110.  
  111. 			if (actual != expected)
  112. 			{
  113. 				string strActual = "was " + (actual ? "accepted" : "not accepted");
  114. 				string strExpected = expected ? "does not contain" : "contains";
  115. 				string errMsg = string.Format("Assertion failure! '{0}' {1} but it {2} '{3}'. input: {4}, regex: {5}, NG-word: {6}", input, strActual, strExpected, ng, input, regex.ToString(), ng);
  116. 				throw new Exception(errMsg);
  117. 			}
  118. 		}
  119. 	}
  120.  
  121. 	internal static class RegexPatternGenerator
  122. 	{
  123. 		public static string GenerateNegativePattern(string ngWord)
  124. 		{
  125. 			if (string.IsNullOrEmpty(ngWord))
  126. 			{
  127. 				throw new Exception();
  128. 			}
  129.  
  130. 			string head = ngWord[0].ToString();
  131. 			if (ngWord.Length == 1)
  132. 			{
  133. 				return string.Format("[^{0}]*", head);
  134. 			}
  135.  
  136. 			string part1 = Part1(ngWord);
  137. 			string part2 = Part2(ngWord);
  138. 			string part3 = Part3(ngWord);
  139. 			string part4 = Part4(ngWord);
  140. 			return string.Format("([^{0}]|{0}({1})*({2}))*(({3}){4})?", head, part1, part2, part3, part4);
  141. 		}
  142.  
  143. 		private static string Part1(string ngWord)
  144. 		{
  145. 			if (ngWord.Length < 2)
  146. 			{
  147. 				throw new Exception();
  148. 			}
  149.  
  150. 			char head = ngWord[0];
  151. 			string result = head.ToString();
  152. 			for (int i = ngWord.Length - 1; 2 <= i; i--)
  153. 			{
  154. 				result = string.Format("{0}|{1}({2})", head, ngWord[i - 1], result);
  155. 			}
  156. 			return result;
  157. 		}
  158.  
  159. 		private static string Part2(string ngWord)
  160. 		{
  161. 			if (ngWord.Length < 2)
  162. 			{
  163. 				throw new Exception();
  164. 			}
  165.  
  166. 			char head = ngWord[0];
  167. 			string result = string.Format("[^{0}{1}]", head, ngWord[ngWord.Length - 1]);
  168. 			for (int i = ngWord.Length - 1; 2 <= i; i--)
  169. 			{
  170. 				result = string.Format("[^{0}{1}]|{1}({2})", head, ngWord[i - 1], result);
  171. 			}
  172. 			return result;
  173. 		}
  174.  
  175. 		private static string Part3(string ngWord)
  176. 		{
  177. 			if (ngWord.Length < 2)
  178. 			{
  179. 				throw new Exception();
  180. 			}
  181. 			else if (ngWord.Length == 1)
  182. 			{
  183. 				return string.Empty;
  184. 			}
  185.  
  186. 			char head = ngWord[0];
  187. 			string part1 = Part1(ngWord);
  188. 			if (ngWord.Length == 2)
  189. 			{
  190. 				return string.Format("{0}*", part1);
  191. 			}
  192. 			else
  193. 			{
  194. 				return string.Format("{0}({1})*", head, part1);
  195. 			}
  196. 		}
  197.  
  198. 		private static string Part4(string ngWord)
  199. 		{
  200. 			if (ngWord.Length < 2)
  201. 			{
  202. 				throw new Exception();
  203. 			}
  204. 			else if (ngWord.Length == 2)
  205. 			{
  206. 				return string.Empty;
  207. 			}
  208.  
  209. 			string result = string.Format("({0})?", ngWord[ngWord.Length - 2]);
  210. 			for (int i = ngWord.Length - 1; 3 <= i; i--)
  211. 			{
  212. 				result = string.Format("({0}{1})?", ngWord[i - 2], result);
  213. 			}
  214. 			return result;
  215. 		}
  216. 	}
  217.  
  218. 	internal static class DirectProductEnumerator
  219. 	{
  220. 		public static IEnumerable<Tuple<T1, T2>> DP<T1, T2>(IEnumerable<T1> set1, IEnumerable<T2> set2)
  221. 		{
  222. 			foreach (var item1 in set1)
  223. 			{
  224. 				foreach (var item2 in set2)
  225. 				{
  226. 					yield return Tuple.Create(item1, item2);
  227. 				}
  228. 			}
  229. 		}
  230.  
  231. 		public static IEnumerable<Tuple<T1, T2, T3>> DP<T1, T2, T3>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3)
  232. 		{
  233. 			foreach (var item1 in set1)
  234. 			{
  235. 				foreach (var item2 in set2)
  236. 				{
  237. 					foreach (var item3 in set3)
  238. 					{
  239. 						yield return Tuple.Create(item1, item2, item3);
  240. 					}
  241. 				}
  242. 			}
  243. 		}
  244.  
  245. 		public static IEnumerable<Tuple<T1, T2, T3, T4>> DP<T1, T2, T3, T4>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3, IEnumerable<T4> set4)
  246. 		{
  247. 			foreach (var item1 in set1)
  248. 			{
  249. 				foreach (var item2 in set2)
  250. 				{
  251. 					foreach (var item3 in set3)
  252. 					{
  253. 						foreach (var item4 in set4)
  254. 						{
  255. 							yield return Tuple.Create(item1, item2, item3, item4);
  256. 						}
  257. 					}
  258. 				}
  259. 			}
  260. 		}
  261.  
  262. 		public static IEnumerable<Tuple<T1, T2, T3, T4, T5>> DP<T1, T2, T3, T4, T5>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3, IEnumerable<T4> set4, IEnumerable<T5> set5)
  263. 		{
  264. 			foreach (var item1 in set1)
  265. 			{
  266. 				foreach (var item2 in set2)
  267. 				{
  268. 					foreach (var item3 in set3)
  269. 					{
  270. 						foreach (var item4 in set4)
  271. 						{
  272. 							foreach (var item5 in set5)
  273. 							{
  274. 								yield return Tuple.Create(item1, item2, item3, item4, item5);
  275. 							}
  276. 						}
  277. 					}
  278. 				}
  279. 			}
  280. 		}
  281.  
  282. 		public static IEnumerable<Tuple<T1, T2, T3, T4, T5, T6>> DP<T1, T2, T3, T4, T5, T6>(IEnumerable<T1> set1, IEnumerable<T2> set2, IEnumerable<T3> set3, IEnumerable<T4> set4, IEnumerable<T5> set5, IEnumerable<T6> set6)
  283. 		{
  284. 			foreach (var item1 in set1)
  285. 			{
  286. 				foreach (var item2 in set2)
  287. 				{
  288. 					foreach (var item3 in set3)
  289. 					{
  290. 						foreach (var item4 in set4)
  291. 						{
  292. 							foreach (var item5 in set5)
  293. 							{
  294. 								foreach (var item6 in set6)
  295. 								{
  296. 									yield return Tuple.Create(item1, item2, item3, item4, item5, item6);
  297. 								}
  298. 							}
  299. 						}
  300. 					}
  301. 				}
  302. 			}
  303. 		}
  304. 	}
  305. }
  306.  
Success #stdin #stdout 0.38s 34992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
==================== NG-word: a ====================
---------- any 2-length word: 4 cases
---------- any 3-length word: 8 cases
---------- any 4-length word: 16 cases
---------- any 5-length word: 32 cases
---------- any 6-length word: 64 cases
==================== NG-word: ab ====================
---------- any 2-length word: 9 cases
---------- any 3-length word: 27 cases
---------- any 4-length word: 81 cases
---------- any 5-length word: 243 cases
---------- any 6-length word: 729 cases
==================== NG-word: abc ====================
---------- any 2-length word: 16 cases
---------- any 3-length word: 64 cases
---------- any 4-length word: 256 cases
---------- any 5-length word: 1024 cases
---------- any 6-length word: 4096 cases
==================== NG-word: abcd ====================
---------- any 2-length word: 25 cases
---------- any 3-length word: 125 cases
---------- any 4-length word: 625 cases
---------- any 5-length word: 3125 cases
---------- any 6-length word: 15625 cases
==================== NG-word: abcde ====================
---------- any 2-length word: 36 cases
---------- any 3-length word: 216 cases
---------- any 4-length word: 1296 cases
---------- any 5-length word: 7776 cases
---------- any 6-length word: 46656 cases
https://ideone.com/Otqvqd
language:
C# (gmcs 5.20.1)
created:
2 years ago
visibility:
secret

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!