#0023. 「ZROI」2020提高组十连测d1t2 palindrome

题目链接

　　http://zhengruioi.com/contest/684/problem/1533

题目解法

　　标题很有用啊！我们可以关注到AA^rA的实质是两个长度为偶数的回文串。很容易想到回文数算法manacher。

　　如果f[i]表示[i-f[i]+1,i+f[i]]这个子串是回文串（处理方法详见manacher算法，维护一个当前r最大的回文串，如果i<=r取对称的值，然后继续检查大于r的部分，因为所有的循环都伴随着r的只增不减，复杂度O(n).）,对于每一个i我们显然要求的是满足以下条件的j的数量：

　　　　j<i && i-j<=f[i] && i-j<=f[j]

　　我们很容易可以得出，以i为第二个回文串中心的AA^rA数量为

(typo error 应该是>=i)

#0023. 「ZROI」2020提高组十连测d1t2 palindrome

原文：https://www.cnblogs.com/myrcella/p/13630135.html