如果我有字符串 A 并且我有许多其他字符串，我想看看是否有任何其他字符串在 A 中。
什么算法可以在尽可能少的迭代中做到这一点？
前任：
'你好，我的名字是鲍勃。'
我想看看是否包含'name is b'，它从[11]开始。
我不想使用正则表达式库。
谢谢
问问题
1543 次
1 回答
7
最有效的算法是Aho-Corasick 算法，它给定一个长度为 n 的字符串和一组总长度为 m 的字符串，可以在 O(n + m + z) 时间内找到所有匹配项，其中 z 是比赛报道。它基于有限自动机，是KMP 字符串匹配算法的推广。
该算法的一个很酷的方面是，如果您有一组固定的关键字和一堆要搜索的文本字符串，则可以通过执行 O(m) 预处理来构建匹配器来加速算法。然后，您可以在 O(n + z) 时间内找到长度为 n 的字符串中的所有匹配项。
另一方面，如果您有一个固定的字符串，然后想要匹配一组不同的模式字符串，请考虑查看后缀树，它提供相同的运行时保证，但如果文本是固定的，则速度更快。
希望这可以帮助！
于 2012-06-05T05:35:11.423 回答