首页 > 笔记 > AC自动机应用总结

AC自动机应用总结


其实发现主要是各种dp

基本上都是一个套路,f[i][j]表示现在的串长为i,现在在ac自动机的j节点,然后从父亲节点转移到所有儿子节点。有时再加一维表示这个状态里面包含了哪些东西(状压)

发现这个转移可以矩乘,也是一个特点。

还有别的题就是在AC自动机上面乱搞,其实可以直接想成Trie图,再想想Trie图,大概都是可以推出来的。

题就是前面的几道,题解也写得挺清楚的,建议按着发的顺序写。先熟悉了简单的dp再加矩乘,还是很套路的。

接下来学学后缀自动机?


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×