string - 在包含子字符串的字符串集中查找字符串的快速方法

Question

任务

我有一个 S 的集合 n = 10,000,000 个字符串 s 并且需要找到集合 S sub>p 包含 S 的字符串 s，其中包含子字符串 p。

简单的解决方案

因为我使用的是 C#，所以使用 LINQ 是一项非常简单的任务:

string[] S = new string[] { "Hello", "world" };
string p = "ll";
IEnumerable<string> S_p = S.Where(s => s.Contains(p));

问题

如果 S 包含许多字符串(如提到的 10,000,000 个字符串)，这会变得非常慢。

想法

建立某种索引以更快地检索 S_p。

问题

为此任务索引 S 的最佳方法是什么？您是否有任何 C# 实现？

Answer 1

这是一种方法:
1. 创建一个字符串 T = S[0] + sep_0 + S[1] + sep_1 + ... + S[n - 1] + sep_n-1(其中 sep_i 是一个独特的字符，对于任何 j 都不会出现在 S[j] 中(如果字符集不够大，它实际上可以是一个整数)) .
2. 为T构建后缀树(线性时间即可完成)。
3. 对每个查询字符串Q遍历后缀树(花费O(length(Q))时间)。然后所有可能的答案都将位于某个子树的叶子中。所以你可以遍历所有这些叶子。如果Q比较长，那么这棵子树的叶子数很可能远小于n。
4. 如果 Q 真的很短，那么子树中的叶子数量可能会非常多。这就是为什么您可以对短查询字符串使用另一种策略:预先计算 S[0] ... S[n - 1] 的所有短子字符串，并为它们中的每一个存储一组索引发生。然后你可以为给定的 Q 打印这些索引。这里很难说“短”的确切含义，但可以通过实验找到。