0

想象有一个很大的字符串 S 数组。从该数组中，我只需要获取那些包含特定子字符串的字符串。例如，如果我的数组是 String s [] = {"hello world", "back to hell", "say hello world"}; 并且我的关键字是“hello”，那么它应该返回我的第一个和最后一个元素。我尝试使用 KMP 和 Boyer-Moor 算法检查数组中的每个字符串是否包含子字符串，但这需要太多时间。然后我了解了 Aho-Corasick 算法。我仍在查找它，但似乎它需要一组子字符串和一个大字符串来匹配，而我想要的恰恰相反。因此，我一直在寻找有关如何为我的目的修改 Aho-Corasick 算法的建议，或其他实现这些目的的方法。将不胜感激任何建议。

4

1 回答 1

1

使用Ukkonen算法或此源（PDF）中建议的算法构建后缀树：

McCreight 的算法可以很容易地适应为集合S={s1, s2, 构建广义后缀树。. . , s_k}个总长度为 N的字符串在O(N)时间内...

然后使用创建的后缀树来搜索给定的模式。问题是在后缀树 T 中找到所有出现的模式 P（长度 m）。根据上述来源：

模式匹配问题可以在最优O(m+k)时间内解决...，其中 k 是 P 在 T 中出现的次数

请注意，文本的长度（或数组中的字符串数）不会影响搜索效率。因此，您可以支付一次构建后缀树的费用，然后多次使用它来有效地搜索短模式字符串。

编辑：如果您赶时间并且不介意一点额外的时间复杂度，您可以使用这种方法（PDF）在 O(n*log^2(n))中构造后缀数组而不是后缀树非常小的一段代码。这是这种方法的核心思想：

该算法主要基于维护字符串后缀的顺序，按其 2^k 长的前缀排序。

这是从上述来源复制的伪代码：

n ←length(T) 
  for i←0 : n – 1
    P(0, i)← position of T(i) in the ordered array of T‘s characters 
cnt ← 1 
for k←1 : [log2n] (ceil)
  for i←0 : n – 1
    L(i)← (P(k – 1, i), P(k – 1, i + cnt), i)             
    sort L
    compute P(k, i) , i = 0, n - 1 
    cnt←2 * cnt

运行此代码后，P将包含后缀数组。使用这种方法进行搜索也很简单：

由于后缀数组提供了 T 的后缀的顺序，因此使用二分搜索很容易将字符串 P 搜索到 T 中。由于比较是在 O(|P|) 中完成的

于 2019-12-23T21:43:59.530 回答