标签为 [回文自动机] 的文章

回文自动机

回文自动机Palindromic Automaton(又称回文树Palindromic Tree,简称pam)能干什么? 对于字符串S[1..n],比如它可以求出S的所有本质不同的回文子串,并求出每一个本质不同的子串在S中出现的次数,当然还能干别的很多事情。 现在来看回文自动机是如何构建的。 定义变量: cnt表示pam中的节点数,pam的每一个节点分别表示一个本质不同的回文串子串 trans[u][c]表示在节点u所对应的回文子串两边加入字符c时变成的回文串对应的节点(可能不存在) len[u]表示节点u表示的回文子串的长度 fail[u]表示结尾与u表示的回文子串相同,长度小 ......

BZOJ3676 [Apio2014]回文串

题目传送门 先来考虑如何快速的求出一个子串的出现次数,那就建一个后缀自动机,预处理出每一个节点的|right(x)|,然后找到子串对应的节点就好了。但是如果从root开始转移的话太慢了,而且不好优化,所以可以尝试倒着来。在建sam的时候顺便记录s[1..x]所对应的节点,对于子串s[l..r],其所对应的节点一定是s[1..r]所对应的点在parent树上的祖先。所以可以倍增求出s[l..r]所对应的节点。 题目还有回文串这个限制,由manacher算法的推论可知一个字符串的本质不同的回文子串只有O(len)个,因为只有当右端点右移的时候的回文串才是之前 ......