AC自动机

基本介绍

AC自动机,正如他的名字,能够让你自动AC(误

其实是一个匹配字符串的算法。

简单来说,就是在trie树上用KMP的思想。

(当然,你也可以理解为就是用了KMP。。

因为本来trie树是可以用来匹配字符串的,但是因为匹配失败的时候都需要从头开始,会导致浪费了很多时间,加大了时间复杂度。

所以,就提出来了AC自动机。

原理就是和KMP的next数组类似,使用一个fail数组,来记录匹配失败之后,需要回溯到哪个地方。

这样便能减少很多复杂度。

时间复杂度为$O(n)$($n$为文本长度)

(AC自动机怎么不能帮助我自动AC啊。。

阅读更多...
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信