前言

距离 2026 CSP 还有 5 天。

---

字符串

就是一串字符。

$\text{Manacher}$

我们一般称它为章子怡算法。 俗称 $\textsf{「马拉车」}$。

Manacher 就是用来求字符串里的回文子串。

就拿这个字符串举例：

字符	$\texttt{a}$	$\texttt{a}$	$\texttt{b}$	$\texttt{c}$	$\texttt{b}$	$\texttt{a}$	$\texttt{a}$

暴力：$\textsf{「中心扩展法」}$

枚举每个回文中心，只要两边字符相同，就继续拓展。例如：当枚举到中间的 $\texttt{c}$ 时，指针 $p$ 和 $q$ 分别向左和向右移动。

字符	$\texttt{a}$	$\texttt{a}$	$\texttt{b}$	$\texttt{c}$	$\texttt{b}$	$\texttt{a}$	$\texttt{a}$
指针	$1$	$2$	$3$	$i$	$5$	$6$	$7$

最后，$p$ 和 $q$ 分别移动到 $1$ 和 $7$。

字符	$\texttt{a}$	$\texttt{a}$	$\texttt{b}$	$\texttt{c}$	$\texttt{b}$	$\texttt{a}$	$\texttt{a}$
指针	$p$	$2$	$3$	$i$	$5$	$6$	$q$

以 $\texttt{c}$ 为中心的最长回文子串长度就是 $7$。

同时要注意，有可能长度是偶数，所以回文中心不是单个字符。

既然是暴力了那时间便自然不好。当所有字符都相同时，时间是 $O(n^2)$ 的。

暴力优化

首先，为了避免奇偶造成的大量分类讨论，可以在所有字符之间都插入一个间隔。就例如 $\texttt{\#}$。然后为了避免复杂的判断出界，可以在左右两端都加上「哨兵」，就是两个不同的字符（首先各自不同，其次不同于字符串内字符）。例如如果字符串只由小写字母组成，那么可以用大写字母。但更好的建议是用一些不可见字符。

不过例题只有小写字母，所以我就用 $\texttt{!}$ 和 $\texttt{?}$ 了。所以 $\texttt{aaa}$ 就会写成：$\texttt{!\#a\#a\#a\#?}$。注意枚举中心的时候不要枚举哨兵。

$\textsf{「蘑菇优化」}$ 我们一般称为「章子怡优化」

定义 $p_i$ 表示以 $i$ 为中心，最长的回文子串半径。

具体方法：在中间的大蘑菇下，蓝色位置（是个 $\texttt{\#}$），其实可以用跟它对称的位置 $1,2$ 之间的 $p$ 值。应为只要在🍄下，就是回文的。

但也有一种情况如下图所示。跟它对称的位置的回文长度能超过🍄的范围。但实际上这一半的回文长度可能没有那么长。所以如果另一边的回文长度超过了🍄的范围，就取🍄的范围。即取较小值。

不过还是有一种情况。这一边的回文长度比另一边还要长。所以这一部分要用中心扩展法解决。

注意如果当前的🍄比最大的🍄大，那就要更新最大的🍄。

#include <iostream>
using namespace std;

const int N = 1.1e7 + 5;
int n, p[N << 1];
string str;

void manacher()
{
    int c = 0, r = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i < r) p[i] = min(p[(c << 1) - i], r - i + 1);
        else p[i] = 1;
        while (str[i - p[i]] == str[i + p[i]]) ++p[i];

        if (i + p[i] > r)
        {
            c = i;
            r = i + p[i] - 1;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    char ch;
    n = 1;
    str = "!#";
    while (cin >> ch)
    {
        str += ch;
        str += '#';
        n += 2;
    }
    str += '?';

    manacher();

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, p[i]);
    cout << ans - 1;
    return 0;
}

时间复杂度是 $O(n)$ 的。