Guest User

Untitled

a guest
Nov 19th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.20 KB | None | 0 0
  1. main();
  2.  
  3. function readfile(file)
  4. {
  5. var fo = new ActiveXObject("Scripting.FileSystemObject");
  6. var f = fo.OpenTextFile(file);
  7. return f.ReadAll();
  8. }
  9.  
  10. function writefile(file, s)
  11. {
  12. var fo = new ActiveXObject("Scripting.FileSystemObject");
  13. var f = fo.OpenTextFile(file, 2, true);
  14. return f.Write(s);
  15. }
  16.  
  17. function brute_force(source, search)
  18. {
  19. var ans = new Array();
  20.  
  21. for (var i = 0; i < source.length - search.length + 1; i++)
  22. {
  23. var j = 0;
  24. while (j < search.length && i + j < source.length && source.charAt(i + j) == search.charAt(j))
  25. j++;
  26.  
  27. if (j == search.length)
  28. ans.push(i);
  29. }
  30.  
  31. return ans;
  32. }
  33.  
  34. function h1(s)
  35. {
  36. var h = 0;
  37. for (var i = 0; i < s.length; i++)
  38. h += s.charCodeAt(i);
  39.  
  40. return h;
  41. }
  42.  
  43. function h2(s)
  44. {
  45. var h = 0;
  46. for (var i = 0; i < s.length; i++)
  47. h += s.charCodeAt(i) * s.charCodeAt(i);
  48.  
  49. return h;
  50. }
  51.  
  52. function sum(source, substr)
  53. {
  54. var ans = new Array();
  55.  
  56. var collisions = 0;
  57.  
  58. var hsub = h1(substr);
  59. var hs = h1(source.substr(0, substr.length));
  60.  
  61. if (hs == hsub)
  62. {
  63. if (source.substr(i, substr.length) != substr)
  64. collisions++;
  65. else
  66. ans.push(0);
  67. }
  68.  
  69. hs = hs - source.charCodeAt(0) + source.charCodeAt(substr.length);
  70.  
  71. for (var i = 1; i < source.length - substr.length + 1; i++)
  72. {
  73. if (hs == hsub)
  74. {
  75. if (source.substr(i, substr.length) != substr)
  76. collisions++;
  77. else
  78. ans.push(i);
  79. }
  80.  
  81. hs = hs - source.charCodeAt(i) + source.charCodeAt(i + substr.length);
  82. }
  83.  
  84. ans.push(collisions);
  85.  
  86. return ans;
  87. }
  88.  
  89.  
  90. function sum2(source, substr)
  91. {
  92. var ans = new Array();
  93.  
  94. var collisions = 0;
  95.  
  96. var hsub = h2(substr);
  97. var hs = h2(source.substr(0, substr.length));
  98.  
  99. if (hs == hsub)
  100. {
  101. if (source.substr(i, substr.length) != substr)
  102. collisions++;
  103. else
  104. ans.push(0);
  105. }
  106.  
  107. hs = hs - source.charCodeAt(0) * source.charCodeAt(0) + source.charCodeAt(substr.length) * source.charCodeAt(substr.length);
  108.  
  109. for (var i = 1; i < source.length - substr.length + 1; i++)
  110. {
  111. if (hs == hsub)
  112. {
  113. if (source.substr(i, substr.length) != substr)
  114. collisions++;
  115. else
  116. ans.push(i);
  117. }
  118.  
  119. hs = hs - source.charCodeAt(i) * source.charCodeAt(i) + source.charCodeAt(i + substr.length) * source.charCodeAt(i + substr.length);
  120. }
  121.  
  122. ans.push(collisions);
  123.  
  124. return ans;
  125. }
  126.  
  127. function robin_karp_hash(s, q, x)
  128. {
  129. var h = 0;
  130.  
  131. var m = 1;
  132. for (var i = 0; i < s.length; i++)
  133. m *= x;
  134.  
  135. for (var i = 0; i < s.length; i++)
  136. {
  137. h += (s.charCodeAt(i) * m) % q;
  138. m /= x;
  139. }
  140.  
  141. return h;
  142. }
  143.  
  144. function robin_karp(source, substr)
  145. {
  146. var ans = new Array();
  147.  
  148. var collisions = 0;
  149.  
  150. var hsub = robin_karp_hash(substr, 13, 1000000007);
  151. var hs = robin_karp_hash(source.substr(0, substr.length), 13, 1000000007);
  152.  
  153. if (hs == hsub)
  154. {
  155. if (source.substr(i, substr.length) != substr)
  156. collisions++;
  157. else
  158. ans.push(0);
  159. }
  160.  
  161. var t = 1;
  162. for (var i = 0; i < substr.length - 1; i++)
  163. t *= 13;
  164.  
  165. hs = ((hs - source.charCodeAt(0) * t) * 13 + source.charCodeAt(substr.length)) % 1000000007;
  166.  
  167. for (var i = 1; i < source.length - substr.length + 1; i++)
  168. {
  169. if (hs == hsub)
  170. {
  171. if (source.substr(i, substr.length) != substr)
  172. collisions++;
  173. else
  174. ans.push(i);
  175. }
  176.  
  177. hs = ((hs - source.charCodeAt(i) * t) * 13 + source.charCodeAt(i + substr.length)) % 1000000007;
  178. }
  179.  
  180. ans.push(collisions);
  181.  
  182. return ans;
  183. }
  184.  
  185.  
  186.  
  187.  
  188. function main()
  189. {
  190. var bruteforce = false;
  191. var hash_summ = false;
  192. var hash_summ_sqr = false;
  193. var hash_rabin_karp = false;
  194. var n = 0;
  195.  
  196. var source = readfile(WSH.Arguments(0));
  197. var substr = readfile(WSH.Arguments(1));
  198.  
  199. for (var i = 2; i < WSH.Arguments.length; i++)
  200. {
  201. if (WSH.Arguments(i) == '-b')
  202. bruteforce = true;
  203. else if (WSH.Arguments(i) == '-h1')
  204. hash_summ = true;
  205. else if (WSH.Arguments(i) == '-h2')
  206. hash_summ_sqr = true;
  207. else if (WSH.Arguments(i) == '-h3')
  208. hash_rabin_karp = true;
  209. else if (WSH.Arguments(i) == '-n')
  210. n = parseInt(WSH.Arguments(i + 1));
  211. }
  212.  
  213. if (bruteforce)
  214. {
  215. var ans = brute_force(source, substr);
  216.  
  217. for (var i = 0; i < ans.length && i < n; i++)
  218. WSH.echo(ans[i]);
  219. }
  220. else
  221. {
  222. var ans = null;
  223.  
  224. if (hash_summ)
  225. ans = sum(source, substr);
  226. else if (hash_summ_sqr)
  227. ans = sum2(source, substr);
  228. else
  229. ans = robin_karp(source, substr);
  230.  
  231.  
  232. for (var i = 0; i < ans.length && i < n; i++)
  233. WSH.echo(ans[i]);
  234.  
  235. if (n < ans.length)
  236. WSH.echo(ans[ans.length - 1]);
  237. }
  238. }
Add Comment
Please, Sign In to add comment