高效的算法来找出一组比赛的短文本

Question

输入：

1. 一个相对较短（100-1000字，通常情况下）的文本。
2. 预先给出约5000个表达式的固定列表，其中大多数表达式长达10-20个字符，其中一些表达式包含其他表达式（例如“尝试”和“再试一次”）。

注意 - 只有第一个输入发生变化，第二个输入发生变化，并且可用于预处理。

所需的输出：

识别表情的所有比赛，从第2项里面的文字。如果匹配含糊不清，尽可能采取贪婪的匹配。

运行时间应该比较快，虽然没有严格的性能要求。这里的暴力尝试可能就足够了。

什么是一个好的算法呢？这里的后缀树是否有用？如何查看所有表达式并将其放入散列表？还请注意，我对实用解决方案感兴趣，因此易于实现可能比超高效算法更有用...

Answer 1

请看Aho–Corasick算法。

Answer 2

假设存储空间不受限制的一般“算法”，用于优化此操作是基于字符构建数据树，使您可以递归搜索您的模式。在构建树索引时，向下遍历，直到达到“唯一”点，“叶”给出该唯一事件发生位置。

在上面的段落中，例如单词“index”出现一次。如果树一次构建一个字符，那么我们遵循的树路径将以“我”字符开始，然后“开始”。如果区分大小写，则只有3次出现（假设，优化和索引）。当我们接下来搜索'd'时，我们遇到了独特的结果。当然，我们可以先从空间开始我们的搜索，然后是我然后是n，我们会沿着不同的路线前进。

您也可以使树不区分大小写，并且您可以在每个分支点使用“nybble”而不是字节。