问题引入：给定一个长度为 $n$ 的字符串 $s$，求其最长回文子串的长度。

当然该问题有多种求解方法：暴力枚举（$O(n^2)$）、字符串哈希（$O(n\log n)$）、Manacher 算法（$O(n)$）等。其中 Manacher 算法以其简单性和高效性著称。

Manacher 算法

我们设 $d_1[i]$ 表示以位置 $i$ 为中心的长度为奇数的回文串个数，$d_2[i]$ 表示以位置 $i$ 为中心的长度为偶数的回文串个数。也可以理解为二者表示了以位置 $i$ 为中心的最长回文串的半径长度。

Manacher 算法可以以线性时间复杂度计算出 $d_1$ 和 $d_2$。

首先我们考虑朴素算法：对每一个中心位置 $i$，在比较一对对应字符后，只要可能，便尝试将答案加 $1$。

vector<int> d1(n), d2(n);
for (int i = 0; i < n; i++) {
    d1[i] = 1;
    while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) d1[i]++;

    d2[i] = 0;
    while (0 <= i - d2[i] && i + d2[i] + 1 < n && s[i - d2[i]] == s[i + d2[i] + 1]) d2[i]++;
}

下文仅以计算 $d_1$ 为例，$d_2$ 的计算方法类似。