JavaScript:检查一个数组是否是另一个数组的子序列(编写更快的朴素字符串搜索算法) [英] JavaScript: check if an array is a subsequence of another array (write a faster naïve string search algo)

问题描述

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

后来我发现维基百科称其为朴素的字符串搜索:

在通常情况下，对于每个错误位置，我们只需查看一个或两个字符即可看到它是错误的位置，因此在一般情况下，这需要O(n + m)步，其中n为干草堆的长度，m是针的长度；但是在最坏的情况下，在"aaaaaaaaab"之类的字符串中搜索"aaaab"之类的字符串会花费O(nm)步.

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.

有人可以用JavaScript编写更快的indexOfArray方法吗?

Can someone write a faster indexOfArray method in JavaScript?

推荐答案

您想要的算法是KMP算法(

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.

我找不到JavaScript实现，但这是其他语言的实现

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.

这篇关于JavaScript:检查一个数组是否是另一个数组的子序列(编写更快的朴素字符串搜索算法)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！