高效的数据结构用于子字符串搜索？

Question

假设我有一组字符串S和一个查询字符串q。我想知道S中的任何一个成员是否是q的子字符串。(对于这个问题，子字符串包括相等的情况，例如"foo"是"foo"的子字符串。) 例如，假设执行我想要的操作的函数称为anySubstring:

S = ["foo", "baz"]
q = "foobar"
assert anySubstring(S, q)  # "foo" is a substring of "foobar"

S = ["waldo", "baz"]
assert not anySubstring(S, q)

有没有一种易于实现的算法，可以在时间复杂度为子线性 len(S) 的情况下完成这个任务？如果需要，将 S 处理成某些巧妙的数据结构也可以，因为我将使用大量 q 字符串查询每个 S，因此此预处理的均摊成本可能是合理的。

编辑：澄清一下，我不关心 S 的哪个成员是 q 的子字符串，只关心是否至少有一个是。换句话说，我只关心布尔型答案。

- dsimcha

---

S中的字符串是否很短？ S中最长字符串的长度与S的长度相比如何？ - aelguindy

Answer 1

我认为Aho-Corasick算法可以实现你想要的功能。我认为还有另一种非常简单的解决方案，就是Rabin-Karp算法。

- aelguindy

---

我不敢相信只有我一个人点赞了正确的答案。 - Nemo

还有一个很好的 #Python 库可以用于 Aho-Corasick https://pypi.org/project/pyahocorasick/！:-D 非常有用的答案！ - alisa

Answer 2

如果S的长度远小于潜在子字符串长度之和，您最好从S中构建一个后缀树，然后在其中进行搜索。这与S的长度加上候选子字符串的总长度成线性关系。当然，由于您至少必须通过所有输入，因此不可能有更好的复杂度算法。如果情况相反，即s的长度大于子字符串的总长度，则最好选择Aho-Corasick算法。希望这可以帮助您。

- Ivaylo Strandjev

---

这适用于另一种方式 - 用单一的“q”进行多次查询，但在这里 - “S”是恒定的，“q”在变化... - amit

@amit 我认为Aho-Corasick可以实现OP想要的功能。它的操作方式与您的解决方案非常相似，只是trie具有失败转换，可以将您带到自动机中的正确位置。 - aelguindy

@aelguindy：我只是在谈论后缀树方法，恐怕我不熟悉提到的算法，但我会在今天稍后阅读它的工作原理。 - amit

@amit 是的，你关于后缀树的评论是正确的，我以为你在评论整个答案，抱歉:-)。 - aelguindy

Answer 3

创建一个正则表达式.*(S1|S2|...|Sn).*并构建其最小化DFA。

通过DFA运行您的查询字符串。

- Dimple Kapadia

---

如果OP完全不关心预处理的效率，那么一旦创建了DFA，所有查询在时间上都是线性的，与S的任何方面无关，仅与q的长度有关。 - aelguindy

@aelguindy，后缀树的工作方式类似，但常数因子和内存占用更少。实际上，你应该将你的DFA最终转换成类似trie的东西。 - Saeed Amiri

@SaeedAmiri 你如何检查查询字符串是否包含后缀树字符串作为子字符串？ 后缀树应该在文本固定时构建，而不是模式。 - aelguindy