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

Question

如果我有字符串A,我有许多其他字符串,我想看看是否有任何其他字符串在A.

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

例如:

'你好,我的名字是鲍勃.'

我想知道'name is b'是否包含在内,它是从[11]开始的.

我不打算使用正则表达式库.

谢谢

Answer 1

最有效的算法是Aho-Corasick算法,它给出一个长度为n的字符串和一组总长度为m的字符串,可以在时间O(n + m + z)中找到所有匹配,其中z是总数比赛报道.它基于有限自动机,是KMP字符串匹配算法的推广.

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

另一方面,如果你有一个固定的字符串,然后想要匹配一组不同的模式字符串,请考虑查看后缀树,它们提供相同的运行时保证,但如果文本是固定的则更快.

希望这可以帮助!