kmp algorithm javascript

Solutions on MaxInterview for kmp algorithm javascript by the best coders in the world

showing results for - "kmp algorithm javascript"
Simon
18 Oct 2018
1var makeKMPTable = function(word) {
2    if(Object.prototype.toString.call(word) == '[object String]' ) {
3        word = word.split('');
4    }
5    var results = [];
6    var pos = 2;
7    var cnd = 0;
8
9    results[0] = -1;
10    results[1] = 0;
11    while (pos < word.length) {
12        if (word[pos - 1] == word[cnd]) {
13            cnd++;
14            results[pos] = cnd;
15            pos++;
16        } else if (cnd > 0) {
17            cnd = results[cnd];
18        } else {
19            results[pos] = 0;
20            pos++;
21        }
22    }
23    return results;
24};
25
26var KMPSearch = function(string, word) {
27    if(Object.prototype.toString.call(string) == '[object String]' ) {
28        string = string.split('');
29    }
30    if(Object.prototype.toString.call(word) == '[object String]' ) {
31        word = word.split('');
32    }
33
34    var index = -1;
35    var m = 0;
36    var i = 0;
37    var T = makeKMPTable(word);
38
39    while (m + i < string.length) {
40        if (word[i] == string[m + i]) {
41            if (i == word.length - 1) {
42                return m;
43            }
44            i++;
45        } else {
46            m = m + i - T[i];
47            if (T[i] > -1) {
48                i = T[i];
49            } else {
50                i = 0;
51            }
52        }
53    }
54    return index;
55};
56
57var test = 'potential';
58
59var string = "This fact implies that the loop can execute at most 2n times. For, in each iteration, it " +
60    "executes one of the two branches in the loop. The first branch invariably increases i and does not " +
61    "change m, so that the index m + i of the currently scrutinized character of S is increased. The second " +
62    "branch adds i - T[i] to m, and as we have seen, this is always a positive number. Thus the location m " +
63    "of the beginning of the current potential match is increased. Now, the loop ends if m + i = n; " +
64    "therefore each branch of the loop can be reached at most k times, since they respectively increase " +
65    "either m + i or m, and m = m + i: if m = n, then certainly m + i = n, so that since it increases by " +
66    "unit increments at most, we must have had m + i = n at some point in the past, and therefore either " +
67    "way we would be done.";
68
69result = KMPSearch(string, test);