ac自动机学习笔记

老规矩,先放资料:
参考资料1
参考资料2
参考资料3

 

(其实这些资料我都没怎么看。。。。因为感觉。。。理解起来非常容易的样子orz)

 

我的理解:感觉这东西如果明白了kmp和trie,理解起来就完全没难度。。。

感觉就是在trie上做kmp…?

nxt数组换个名字叫fail。。。。其实是一样的东西吧。。。?

来来来,先干一波题再回来总结。。。

 

感觉暴力匹配相对于kmp(都是线性单模式串),就好像trie相对于ac自动机(都是树上多模式串)

另一个方向:暴力相对于trie,(都是暴力)就好像kmp相对于ac自动机(都是经过失配优化)

ac自动机的题目里这么多和dp结合在一起让我怎么做啊orz…

以及感觉。。。ac自动机的水平可以通过多写trie来提高2333。

区域赛之前再刷一波trie…

是时候干掉线段树了。。。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz