POJ3974 Palindrome

写几个回文串观察它们的性质，我们可以发现回文串分为两类。

奇回文串 $A[1 \sim M]$，长度 $M$ 为奇数，并且 $A[1 \sim M / 2 + 1] = \text{reverse}(A[M / 2 + 1 \sim M])$，它的中心点是一个字符。其中 $\text{reverse}(A)$ 表示把字符串 $A$ 倒过来。

偶回文串 $B[1 \sim M]$，长度 $M$ 为偶数，且 $B[1 \sim M / 2] = reverse(B[M / 2 + 1 \sim M])$，它的中心点是两个字符之间的夹缝。

于是在本题中，我们可以枚举 $S$ 的回文字串的中心位置 $i = 1 \sim N$，看从这个中心位置出发向左右两侧最长可以扩展出多长的回文串。也就是说：

1. 求出一个最大的整数 $p$ 使得 $S[i - p \sim i] = \text{reverse}(S[i \sim i + p])$，那么以 $i$ 为中心的最长奇回文字串的长度就是 $2 * p + 1$；
2. 求出一个最大的整数 $q$ 使得 $S[i - q \sim i - 1] = \text{reverse}(S[i \sim i + q - 1])$，那么以 $i - 1$ 和 $i$ 之间的夹缝为中心的最长偶回文字串的长度就是 $2 * 1$。

我们知道在 $\mathcal{O}(N)$ 预处理前缀 $\text{Hash}$ 值后，可以 $\mathcal{O}(1)$ 计算任意字串的 $\text{Hash}$ 值。类似地，我们可以倒着做一遍预处理，就可以 $\mathcal{O}(1)$ 计算任意字串倒着读的 $\text{Hash}$ 值。于是我们可以对 $p$ 和 $q$ 进行二分答案，用 $\text{Hash}$ 值 $\mathcal{O}(1)$ 比较一个正着读的字串和一个倒着读的字串是否相等，从而在 $\mathcal{O}(\log N)$ 时间内求出最大的 $p$ 和 $q$。在枚举过的所有中心位置对应的奇、偶回文字串长度中取 $\max$ 就是整道题目的答案，时间复杂度为 $\mathcal{O}(N \log N)$。