hackerrank Circular Palindromes

题意

给出(n)长度字符串，(n)次循环形成的(n)长度字符串，分别求最长回文长度。

做法

比较暴力的做法就是PAM然后前端删除后端插入，不会这种科技...

将字符串(S)拼接成(SS)，对于其中任意长度为(n)的字符串(T)，其回文串形式分为三种

• 前缀
• 后缀
• 真子串

跑一边manacher，然后真子串可以用线段树，下面考虑前缀（后缀类似）
令(f_i)为以(i)开头的最长回文串，这样manacher跑出来后存在最开头，则(f_i=max(f_i,f_{i-1}-2))