在另一个字符串中搜索字符串数组的最有效方法

Question

我有一大堆字符串,看起来像这样:String temp [] = new String [200000].

我有另一个字符串,让我们称它为bigtext.我需要做的是遍历temp的每个条目,检查是否在bigtext中找到该条目,然后根据它进行一些工作.所以,骨架代码看起来像这样:

for (int x = 0; x < temp.length; x++) {
  if (bigtext.indexOf(temp[x]) > -1 {

  //do some stuff
  } else continue;
}

因为temp中有很多条目,并且有很多bigtext实例,所以我想以最有效的方式做到这一点.我想知道如果有更好的方法可以做到这一点,我所概述的是最有效的方法来迭代搜索.

谢谢,

埃利奥特

Answer 1

我认为你正在寻找像Rabin-Karp 或Aho-Corasick这样的算法,它们可以并行搜索文本中的大量子字符串.

Answer 2

请注意,您当前的复杂性是O(|S1|*n),数组|S1|的长度bigtext和n数量是多少,因为每次搜索都是实际的O(|S1|).

通过从数组中的元素构建后缀树bigtext,并迭代数组中的元素,您可以将此复杂性降低到O(|S1| + |S2|*n),其中|S2|是数组中最长字符串的长度.假设|S2| << |S1|,它可能会快得多!

构建后缀树是O(|S1|),每次搜索都是O(|S2|).您不必bigtext在后缀树的相关部分上查找它.由于它是完成n时间,你得到的总数,渐渐O(|S1| + n*|S2|)地比天真的实现更好.

Answer 3

如果您有其他信息temp,可以改进迭代.

如果并行化迭代,还可以减少花费的时间.

Answer 4

效率在很大程度上取决于对您有价值的东西.

你是否愿意增加记忆以缩短时间？您是否愿意增加有效处理大型数据集的时间？您是否愿意增加对CPU内核的争用？您是否愿意进行预处理(可能是一种或多种形式的索引)以减少关键部分的查找时间.

随着您的提供,您指出您想要的整个部分更有效,但这意味着您已经排除了可以进行权衡的代码或系统的任何部分.这迫使人们想象你关心什么以及你不关心什么.根据一个人的观点,所有发布的答案都是正确和不正确的赔率非常高.