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

arrays performance algorithm java

2022-09-02 11:43:17

我有一大堆字符串，看起来像这样：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;
}

因为临时条目太多，也有很多大文本实例，所以我想以最有效的方式做到这一点。我想知道我所概述的是否是迭代搜索是否有更好的方法来做到这一点的最有效方法。

谢谢

埃利奥特

答案 1

我认为您正在寻找像Rabin-Karp或Aho-Corasick这样的算法，这些算法旨在并行搜索文本中的大量子字符串。

答案 2

请注意，您当前的复杂度是，其中是数组中元素的长度和数量，因为每次搜索实际上都是。O(|S1|*n)|S1|bigtextnO(|S1|)

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

构建后缀树是，每个搜索都是。您不必通过即可找到它，只需在后缀树的相关部分上即可。由于它是完成次数，因此您得到 total of ，这比朴素实现渐近更好。O(|S1|)O(|S2|)bigtextnO(|S1| + n*|S2|)