JavaScript:检查一个数组是否是另一个数组的子序列(编写一个更快的天真字符串搜索algo)
JavaScript:检查一个数组是否是另一个数组的子序列(编写一个更快的天真字符串搜索algo)
提问于 2011-02-12 11:32:06
[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是干草堆的长度，m是针的长度；但在最坏的情况下，搜索像“aaaaaaaaab”的字符串像"aaaaaaaaab"，它采取O(nm)步骤。
有人能用indexOfArray编写更快的JavaScript方法吗？
回答 2
Stack Overflow用户
发布于 2011-02-12 11:37:59
Stack Overflow用户
发布于 2011-02-12 12:02:08
FWIW:我发现这篇文章很好地阅读了高效子串搜索，它讨论了Boyer的几个变体，尽管它不在JavaScript中。博耶-摩尔-霍斯波尔变体(由Timo‘s --参见链接的第一个链接)将是我对潜在的实际速度增益的“建议”(不减少大-O，但-大-大-O只是上限！)注意文章末尾的结论和上面的基准。
我主要是想反对Knuth-Morris-Pratt的实施;-)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4980134
复制相关文章
相似问题
腾讯云开发者
