【施工中】回文自动机学习笔记

是14年才被提出来的算法…
先%一下该算法的作者:作者的codeforces页

接下来,老规矩,放一波资料:

参考博客1
codeforces上的讲解

 

20171115 update:

emmmm,这篇是学习笔记是16年9月写的。。。。一转眼13个月过去了啊。。

回文树,也叫回文自动机,简称PAM

学了SAM之后PAM简直是傻逼算法…

该算法时间和空间复杂度都是O(n)

这样的复杂度基于以下结论:

长度为n的字符串的本质不同的回文串的数目不超过n

因此状态数开到和字符串长度一样就可以了orz

 

len表示某个状态所表示的回文串的长度

cnt表示某个状态所表示的回文串的数量

构建PAM的算法仍然是增量算法,在某一时刻,本质不同的回文串的数量是sz-1 (sz标号从0开始,出去标号为0和标号为1的2个根)

 

唯一需要特别注意的是

在构建完PAM之后,沿着回文链(类比后缀链)从底向上跑一遍得到的cnt,才是真正的cnt

在构建完PAM之后,沿着回文链(类比后缀链)从底向上跑一遍得到的cnt,才是真正的cnt

在构建完PAM之后,沿着回文链(类比后缀链)从底向上跑一遍得到的cnt,才是真正的cnt

我的模板:

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz