从列表中搜索缓冲区中任何字符串的高效算法

Question

我正在寻找一种高效的搜索算法，对于给定的一组字符串，可以从字符串集合中搜索一个大的缓冲区来匹配任何一个字符串。目前，我知道一些有效的单字符串算法(我以前使用过Knuth )，但我不知道它们是否真的有帮助。

以下是我实际上正在做的事情：

• 我有大约6-10个预定义字符串，每个字符串大约有200-300个字符(实际上是字节，因为我在处理二进制数据)。
• 输入是一个大的，有时是几兆字节的缓冲区。
• 我想要处理缓冲区，当我有匹配时，我想停止搜索。

我使用一组有限的预定义模式寻找多字符串搜索算法，但它们似乎都围绕着匹配缓冲区中的所有预定义字符串。

这篇文章：Fast algorithm for searching for substrings in a string，建议使用alogirthm或Rabin。

我想，由于我只需要一个匹配，我可以找到其他方法，类似于上述算法，但问题的约束可以提高性能。

Answer 1

阿波罗-科拉西克是个不错的选择。在构建了一个自动机之后，输入字符串将从左到右遍历，因此在找到第一个匹配后立即停止是可能的。时间复杂度是O(所有模式的长度之和+第一次出现的位置)。这是最优的，因为在第一次出现之前，如果不从缓冲区读取所有模式和所有字节，就不可能找到第一个匹配。