hdu 2896 病毒侵袭 (ac自动机)

hdu 2896 题目链接

 

题意:给出n个病毒,然后给出m个网站,然后问每个网站中有哪些病毒,以及有病毒的网站的个数。

需要注意病毒和网站都需要按从小到达排列输出。

思路:ac自动机,需要记录病毒id…然后。。因为病毒的id忘记排序wa了好多发。。智力减2.

 

 

 

 

ac自动机模板by Lalatina (hdu 2222)

orzorz 日常%学弟 华科的未来orz

hdu 2222 Keywords Search (ac自动机模板题(静态数组写法+动态指针写法))

hdu 2222 题目链接

题意:给出n个模式串,一个文本串,问文本串中出现了多少各模式串。

思路:ac自动机裸题。代码风格来自bin神。静态数组的写法。

需要理解 在build fail的时候,先单独处理root的必要性。

 

讲真。。觉得上面的代码写的丑(bin神的粉丝别打我T T)
于是换成了自己改成了动态的写法。。

 

 

 

ac自动机学习笔记

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

 

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

 

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

感觉就是在trie上做kmp…?

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

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

 

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

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

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

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

区域赛之前再刷一波trie…

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