javascript - 有效搜索较大字符串中的多个子字符串之一

Question

我正在寻找一个函数，该函数可以从较长字符串(“haystack”)中的字符串数组(“needles”)中找到一个子字符串。基本上我希望它像这个例子一样工作:

var haystack = "abcdefghijklmnopqrstuvwxyz";
var needles = [
  'bcd',
  'pqr',
  'hi',
  'ghi',
  'g',
  'stuv'
  ];

var output = findSubstring (haystack, needles, 2, 20);

输出现在应该有:

 {index: 6, which: 3}

这意味着它在位置 6 找到了“ghi”(针 3)。它得到的是“ghi”而不是“hi”，因为“ghi”在大海捞针中开始得较早，但它没有得到“g”，因为“ghi' 在针阵列中较早。

这是我想出的最好的方法，但它在处理非常大的文本 block 和非常大的针阵列(我正在使用它)时似乎相当慢，而且我相信还有更好的东西.这是非常关键的性能，所以我真的想要更快的东西。

我可以想象更好的方法来做到这一点(可能不使用 indexOf)，并且由于这(大概)是一种很常见的事情，对这种事情有更多经验的人可能有更好的方法关于它。 (即我宁愿不重新发明轮子)

function findSubstring (haystack, needles, startIndex, endIndex) {
  var min = Infinity, best = -1;
  var numNeedles = needles.length;
  if (!startIndex)
    startIndex = 0;

  for (var i=0; i<numNeedles; i++) {
    var index = haystack.indexOf(needles[i], startIndex);
    if (index != -1 && index < min) {
      min = index;
      best = i;
    }
  }
  return (best == -1 || (endIndex && best >= endIndex)) ?
      null : 
      {index: min, which: best};
}

Answer 1

建议将您的针组合成一个正则表达式:“bcd|pqr|hi|ghi|g|stuv”。

正则表达式引擎会将它们组合成一个高效的有限状态机。