检查字符串是否包含另一个字符串算法？

Question

如果我有字符串A，并且我有许多其他字符串，并且我想查看是否有任何其他字符串在A中。

什么算法可以在尽可能少的迭代中做到这一点？

例如：

'您好，我的名字是鲍勃。'

我想看看是否包含'name is b'，它是从[11]开始的。

我不想使用正则表达式库。

由于

Answer 1

对此最有效的算法是Aho-Corasick algorithm，其给定长度n的串并设置的总长度为m的字符串可以找到在时间为O所有比赛（N + M + Z），其中z是报告的总数。它基于有限自动机，是KMP string matching algorithm的推广。

这个算法的一个很酷的方面是，如果你有一组固定的关键字和一堆你想要搜索的文本字符串，那么算法可以通过O（m）预处理来加速建立匹配器。然后，您可以在时间O（n + z）中找到长度为n的字符串中的所有匹配项。

另一方面，如果您有一个固定字符串，然后想要匹配一组不同的模式字符串，请考虑查看suffix trees，它们给出了相同的运行时间保证，但是如果文本是固定的，则速度会更快。

希望这会有所帮助！