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

本文介绍了JavaScript:检查一个数组是否是另一个数组的子序列(编写更快的朴素字符串搜索算法)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 [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算法( en.wikipedia/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm )用于查找以下内容的起始索引字符串中的子字符串-您可以对数组执行完全相同的操作.

The algorithm you want is the KMP algorithm (en.wikipedia/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实现，但这是其他语言的实现 zh.wikibooks/wiki/Algorithm_implementation/String_searching/Knuth-Morris-Pratt_pattern_matcher －将一个人转换为js并不难.

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