algorithm - 在短文本中查找一组匹配项的高效算法

Question

输入:

1. 相对较短(通常为 100-1000 个字符)的文本。
2. 预先给出的约 5000 个表达式的固定列表，其中大部分长度为 10-20 个字符，其中一些包含其他表达式作为子表达式(例如“Try”和“Try Again”)。

注意 - 只有第一个输入发生变化，第二个被认为是常量，可用于预处理。

期望的输出:

识别文本中第 2 项中表达式的所有匹配项。如果存在匹配歧义，尽可能采用贪心匹配。

运行时应该相对较快，但没有严格的性能要求。在这里，暴力尝试可能就足够了。

对此有什么好的算法？后缀树在这里有用吗？遍历所有表达式并将它们放入哈希表中怎么样？另请注意，我对实用解决方案很感兴趣，因此易于实现可能比超高效算法更有用...

Answer 1

看看 Aho–Corasick算法。