Manacher+回文自动机 专题训练 字符串 数学

Manacher+回文自动机 专题训练

本来计划着刷完网络流马上去博弈论的,可是做了两道题之后发现有点做不动了,就先花了半天来复习字符串,顺便把之前的坑都填上。 BZOJ2342 [Shoi2011]双倍回文 这道题用回文自动机应该是比较简单。因为满足要求的1/2回文串节点一定在当前节点的fail指针指向的祖先中,所以只需要建出回文自动机···
BZOJ3676 [Apio2014]回文串 回文自动机 字符串

BZOJ3676 [Apio2014]回文串 回文自动机

回文自动机裸题。 空间复杂度:O(n*(字符集大小)),时间复杂度:O(n*log(字符集大小))。 可实现的操作: 1.求字符串前缀中本质不同的回文串的个数。 2.求每一个本质不同回文串出现的次数。 3.求所有的回文串数。 4.求以特定下标为结尾的回文串数。 同时求出回文串的长度。 直接上代码,具···