目录

Chapter-11 TextMatch 第11章 文本匹配 - ACAutomation AC自动机

优质
小牛编辑
126浏览
2023-12-01

问题

在文本 text 中查找 k 个字符串 str 出现的所有位置,其中 text 长度为 n , str 长度为 m 。

如果使用SimpleMatch或KMPMatch,我们需要对每一个字符串 str[i] (其中 0 le i lt k )都执行一遍匹配算法,对于长度为 n 的文本 text ,一次匹配算法的时间复杂度最小为 O(n) (KMPMatch),那么整个过程的时间复杂度为 O( n times k ) 。

AC自动机算法可以在遍历一次文本 text 中找出 k 个字符串的所有位置,时间复杂度接近 O(n) 。

解法