标签为 [manacher] 的文章

BZOJ3676 [Apio2014]回文串

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