Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- main();
- function readfile(file)
- {
- var fo = new ActiveXObject("Scripting.FileSystemObject");
- var f = fo.OpenTextFile(file);
- return f.ReadAll();
- }
- function writefile(file, s)
- {
- var fo = new ActiveXObject("Scripting.FileSystemObject");
- var f = fo.OpenTextFile(file, 2, true);
- return f.Write(s);
- }
- function brute_force(source, search)
- {
- var ans = new Array();
- for (var i = 0; i < source.length - search.length + 1; i++)
- {
- var j = 0;
- while (j < search.length && i + j < source.length && source.charAt(i + j) == search.charAt(j))
- j++;
- if (j == search.length)
- ans.push(i);
- }
- return ans;
- }
- function h1(s)
- {
- var h = 0;
- for (var i = 0; i < s.length; i++)
- h += s.charCodeAt(i);
- return h;
- }
- function h2(s)
- {
- var h = 0;
- for (var i = 0; i < s.length; i++)
- h += s.charCodeAt(i) * s.charCodeAt(i);
- return h;
- }
- function sum(source, substr)
- {
- var ans = new Array();
- var collisions = 0;
- var hsub = h1(substr);
- var hs = h1(source.substr(0, substr.length));
- if (hs == hsub)
- {
- if (source.substr(i, substr.length) != substr)
- collisions++;
- else
- ans.push(0);
- }
- hs = hs - source.charCodeAt(0) + source.charCodeAt(substr.length);
- for (var i = 1; i < source.length - substr.length + 1; i++)
- {
- if (hs == hsub)
- {
- if (source.substr(i, substr.length) != substr)
- collisions++;
- else
- ans.push(i);
- }
- hs = hs - source.charCodeAt(i) + source.charCodeAt(i + substr.length);
- }
- ans.push(collisions);
- return ans;
- }
- function sum2(source, substr)
- {
- var ans = new Array();
- var collisions = 0;
- var hsub = h2(substr);
- var hs = h2(source.substr(0, substr.length));
- if (hs == hsub)
- {
- if (source.substr(i, substr.length) != substr)
- collisions++;
- else
- ans.push(0);
- }
- hs = hs - source.charCodeAt(0) * source.charCodeAt(0) + source.charCodeAt(substr.length) * source.charCodeAt(substr.length);
- for (var i = 1; i < source.length - substr.length + 1; i++)
- {
- if (hs == hsub)
- {
- if (source.substr(i, substr.length) != substr)
- collisions++;
- else
- ans.push(i);
- }
- hs = hs - source.charCodeAt(i) * source.charCodeAt(i) + source.charCodeAt(i + substr.length) * source.charCodeAt(i + substr.length);
- }
- ans.push(collisions);
- return ans;
- }
- function robin_karp_hash(s, q, x)
- {
- var h = 0;
- var m = 1;
- for (var i = 0; i < s.length; i++)
- m *= x;
- for (var i = 0; i < s.length; i++)
- {
- h += (s.charCodeAt(i) * m) % q;
- m /= x;
- }
- return h;
- }
- function robin_karp(source, substr)
- {
- var ans = new Array();
- var collisions = 0;
- var hsub = robin_karp_hash(substr, 13, 1000000007);
- var hs = robin_karp_hash(source.substr(0, substr.length), 13, 1000000007);
- if (hs == hsub)
- {
- if (source.substr(i, substr.length) != substr)
- collisions++;
- else
- ans.push(0);
- }
- var t = 1;
- for (var i = 0; i < substr.length - 1; i++)
- t *= 13;
- hs = ((hs - source.charCodeAt(0) * t) * 13 + source.charCodeAt(substr.length)) % 1000000007;
- for (var i = 1; i < source.length - substr.length + 1; i++)
- {
- if (hs == hsub)
- {
- if (source.substr(i, substr.length) != substr)
- collisions++;
- else
- ans.push(i);
- }
- hs = ((hs - source.charCodeAt(i) * t) * 13 + source.charCodeAt(i + substr.length)) % 1000000007;
- }
- ans.push(collisions);
- return ans;
- }
- function main()
- {
- var bruteforce = false;
- var hash_summ = false;
- var hash_summ_sqr = false;
- var hash_rabin_karp = false;
- var n = 0;
- var source = readfile(WSH.Arguments(0));
- var substr = readfile(WSH.Arguments(1));
- for (var i = 2; i < WSH.Arguments.length; i++)
- {
- if (WSH.Arguments(i) == '-b')
- bruteforce = true;
- else if (WSH.Arguments(i) == '-h1')
- hash_summ = true;
- else if (WSH.Arguments(i) == '-h2')
- hash_summ_sqr = true;
- else if (WSH.Arguments(i) == '-h3')
- hash_rabin_karp = true;
- else if (WSH.Arguments(i) == '-n')
- n = parseInt(WSH.Arguments(i + 1));
- }
- if (bruteforce)
- {
- var ans = brute_force(source, substr);
- for (var i = 0; i < ans.length && i < n; i++)
- WSH.echo(ans[i]);
- }
- else
- {
- var ans = null;
- if (hash_summ)
- ans = sum(source, substr);
- else if (hash_summ_sqr)
- ans = sum2(source, substr);
- else
- ans = robin_karp(source, substr);
- for (var i = 0; i < ans.length && i < n; i++)
- WSH.echo(ans[i]);
- if (n < ans.length)
- WSH.echo(ans[ans.length - 1]);
- }
- }
Add Comment
Please, Sign In to add comment