JavaScript:检查数组是否是另一个数组的子序列(写一个更快的天真字符串搜索算法)

Question

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

我想出了这个:

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;
};

后来我发现维基百科称之为Naïve字符串搜索:

在正常情况下,我们只需要查看每个错误位置的一个或两个字符,看它是一个错误的位置,所以在一般情况下,这需要O(n + m)步,其中n是长度干草堆和米是针的长度; 但在最坏的情况下,在像"aaaaaaaaab"这样的字符串中搜索像"aaaab"这样的字符串,需要O(nm)步.

有人可以在JavaScript中编写更快的indexOfArray方法吗？

Answer 1

你想要的算法是KMP算法(http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm),用于查找字符串中子字符串的起始索引 - 你可以为数组做同样的事情.

我找不到javascript实现,但这里是其他语言的实现http://en.wikibooks.org/wiki/Algorithm_implementation/String_searching/Knuth-Morris-Pratt_pattern_matcher - 将一个转换为js应该不难.