P3805 【模板】Manacher 题解

manacher 算法通常用来在 $O(n)$ 时间复杂度内求解字符串最长回文子串 / 以串内一点为中心的最长回文半径问题。

一些前置定义：

• 回文串：定义一个长度为 $n$ 下标从 $1$ 开始的字符串 $s$ 是回文的，当且仅当 $\forall i\in[1,n]\cap\mathbb{N_+},s_i=s_{n-i+1}$。
• 回文子串：定义串 $t$ 是串 $s$ 的回文子串，当且仅当 $t$ 为回文串，且 $t$ 为 $s$ 的子串。
• 最长回文子串：定义一个长度为 $n$ 的字符串的最长回文子串，为其所有回文子串中长度最长的子串。
• 最长回文半径：定义一个长度为 $n$ 下标从 $1$ 开始的字符串 $s$ 在 $i$ 位置的最长回文半径 $j$ 是最大的整数满足 $\forall k\in[0,j),(s_{i+k}=s_{i-k})\land (i+k\le n)\land (i-k\ge 1)$。
• 回文中心：定义一个长度为 $n$ 下标从 $1$ 开始的回文串 $s$ 的回文中心：若 $n$ 为奇数则 $s$ 串的回文中心位于 $\frac{n+1}2$，否则回文中心位于 $\frac n2$ 和 $\frac n2+1$ 两位置之间。

问题求解：

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

Data Range: $1\le n\le 1.1\times 10^7$。

算法流程：

这里认为 $s$ 串下标从 $1$ 开始。

设 $p_i$ 表示 $i$ 位置处最长回文半径的长度。由于存在长度为偶数的回文串，此时回文中心位于两字符之间，为了方便处理，在这里对原字符串进行一次特殊的操作：即将原字符串中任意两字符之间，以及头尾两处均添加一个特殊字符（例如：$）。此时字符串长度由 $n$ 变为 $2n+1$，原来的每一个长度为偶数的回文串均变为由特殊字符为回文中心的回文串。例如：串 abcbaab 变为 $a$b$c$b$a$a$b$，此时串 abcba 变为 $a$b$c$b$a$，以 c 字符为回文中心；串 baab 变为 $b$a$a$b$，以两个 a 字符之间的 $ 为回文中心。

然后考虑求解 $p$ 数组。首先思考怎么暴力求解。很容易想到对于字符串的每一个 $i$ 都暴力向左向右扩展直到左右两侧的字符不相同为止。期望跑的很快，但是很明显可以被形如 aa....a 的字符串给卡到 $O(n^2)$。这样做很多判断的信息都被浪费掉重新又判断了一遍，因此考虑类似于 kmp，利用这些信息优化计算 $p$ 数组的时间复杂度。

从左往右按顺序依次枚举每一个 $i$。假设当前已经处理了 $p_1,p_2,\ldots,p_{i-1}$ 要计算 $p_i$ 的值。我们记录 r 和 nowmid 两个信息分别表示以 $1\sim i-1$ 为回文中心时，回文中心可以覆盖到的下标最大的点下标最大是多少（r）以及此时回文中心的下标是多少（nowmid）。

然后分类讨论 $i$ 和 r 之间的关系：

1. $i>r$

直接暴力扩展更新答案即可。

2. $i\le r$

考虑如何快速的计算 $p_i$ 的值：此时已经计算得到存在一个以 nowmid 为回文中心的回文串，其回文半径覆盖的下标最大的点下标为 r，那么同样可以直接计算出覆盖的下标最小的点下标为 l。此时容易对称的计算 $i$ 关于 nowmid 对称的点下标为 $j$，则此时已经计算出以 $j$ 点为中心的回文半径长度，直接用 $p_j$ 的值更新 $p_i$ 即可。

但是若此时 $p_i$ 的值超过了当前回文串半径 r，那么超过的部分由于不在回文串内不能保证回文，因此只能将 $p_i$ 更新到 $r-i+1$，然后继续暴力扩展。同样的，若 $p_i$ 的值恰好为 $r-i+1$，那么也不能保证为最长回文串，也需要继续暴力扩展。有一个简单的写法是更新完 $p_i$ 的值之后直接暴力扩展（容易发现剩下不能扩展的情况暴力扩展的时间复杂度为 $O(1)$）。计算完 $p_i$ 后，更新 r 和 nowmid 的值即可。

代码实现：

int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i)
        t[i * 2] = s[i], t[i * 2 + 1] = '$';
    t[1] = '$';
    n = n * 2 + 1;
    for (int i = 1; i <= n; ++i)
        s[i] = t[i];
    int r = 0, nowmid = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i < r)
            p[i] = min(p[2 * nowmid - i], r - i);
        else
            p[i] = 1;
        while (i + p[i] <= n && i - p[i] >= 1 && s[i + p[i]] == s[i - p[i]])
            ++p[i];
        if (p[i] + i > r)
            r = i + p[i], nowmid = i;
    }
    cout << *max_element(p + 1, p + n + 1) - 1 << '\n';
    return 0;
}

时间复杂度分析：

很显然除了暴力更新的部分以外时间复杂度都是 $O(n)$，而暴力更新部分最多扩展 $n$ 次（扩展之后 r 会变大，但是 r 不会变小，最多从 $1$ 变到 $n$），因此总时间复杂度为 $O(n)$。空间复杂度也为 $O(n)$，可以通过。