JavaScript: check if an array is a subsequence of another array (write a faster naïve string search algo)

Question

[5, 4, 4, 6].indexOfArray([4, 6]) // 2
['foo', 'bar', 'baz'].indexOfArray(['foo', 'baz']) // -1

I came up with this:

Array.prototype.indexOfArray = function(array) {
    var m = array.length;
    var found;
    var index;
    var prevIndex = 0;
    while ((index = this.indexOf(array[0], prevIndex)) != -1) {
        found = true;
        for (var i = 1; i < m; i++) {
            if (this[index + i] != array[i]) {
                found = false;
            }
        }
        if (found) {
            return index;
        }
        prevIndex = index + 1
    }
    return index;
};

Later I have find wikipedia calls it Naïve string search:

In the normal case, we only have to look at one or two characters for each wrong position to see that it is a wrong position, so in the average case, this takes O(n + m) steps, where n is the length of the haystack and m is the length of the needle; but in the worst case, searching for a string like "aaaab" in a string like "aaaaaaaaab", it takes O(nm) steps.

Can someone write a faster indexOfArray method in JavaScript?

Answer 1

The algorithm you want is the KMP algorithm (http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) used to find the starting index of a substring within a string -- you can do exactly the same thing for an array.

I couldn't find a javascript implementation, but here are implementations in other languages http://en.wikibooks.org/wiki/Algorithm_implementation/String_searching/Knuth-Morris-Pratt_pattern_matcher -- it shouldn't be hard to convert one to js.

Answer 2

FWIW: I found this article a good read Efficient substring searching It discusses several variants of Boyer-Moore although it's not in JavaScript. The Boyer-Moore-Horspool variant (by Timo Raita’s -- see first link for link) was going to be my "suggestion" for a potential practical speed gain (does not reduce big-O though -- big-O is upper limit only!). Pay attention to the Conclusion at the bottom of the article and the benchmarks above.

I'm mainly trying to put up opposition for the Knuth-Morris-Pratt implementation ;-)