题目 | Prefix-Suffix Palindrome (Hard version)
Codeforces Global Round 7
D2. Prefix-Suffix Palindrome (Hard version)
算法 | Manacher
Manacher (manachar, 马拉车)：在 $O(n)$ 时间内计算一个字符串内所有回文子串的算法。
算法 | 字符串哈希
字符串哈希：定义一种将字符串映射到一个整型哈希值的函数 $f(\cdot)$，我们希望这个函数可以方便地帮我们判断两个字符串是否相等。