题解：P3805 【模板】manacher

· · 题解

题解：P3805 【模板】manacher

真是有意思的算法捏，呵呵

解法

很容易能想到 O(n^2) 的算法，就是选取一个位置 i 向两边扩展即可。

首先，我们需要对数据做一个小小的改变，因为一个回文串的对称中心不一定是整数，所以我们要想办法将其变成整数。所以，我们可以把它的每两个字符中间加上一个相同的特殊字符（这里指原串中不会出现的字符），例如，aaa 可以变成 aAaAa，这样，对称中心就一定是在一个整数位上了。但是，我们还要处理一个边界问题，解决方法是将原串前加一个特殊字符，比如，aaa 要变成 BaAaAa，这个其实是为了防止越界。

为了方便，我们设 rad_i 为以 i 为对称中心的最长回文半径，l、r 和 mid 分别为已知的最靠右的回文串的左右边界与它的对称中心。

我们发现，在 O(n^2) 的算法中，有许多扩展是不必要的，对此，我们开始分类讨论。

情况 1：i \le r

我们设 j 为 i 在对称中心为 mid 的情况下的对称点。把字符串位置设想成一个数轴，那么 (i+j) \div 2 = mid，所以 j 的位置为 2 \times mid - i。

因为 [l,r] 是回文的，所以区间 [j-rad_j,j+rad_j] 和区间 [i-rad_i,i+rad_i] 是相等的，又因为 [j-rad_j,j+rad_j] 是回文串，所以 [i-rad_i,i+rad_i] 是回文串，所以，我们知道，rad_i 是可以取到 rad_j 的。但是，这一切的前提都建立在 i+rad_j \le r 的前提下的，若 i+rad_j > r，那么，我们就不能保证 rad_i = rad_j，所以只能取到 r-i+1。

综上，rad_i= \min(rad_j, r-i+1)。然后，暴力扩展即可。

情况 2：i > r

这种情况我们只能由 rad_i = 1 开始一步步扩展。

由此，我们就以 O(n) 的复杂度完成了题目。

时间复杂度

让我们来看看它的时间复杂度为啥是 O(n) 的（相信这个地方难倒了许多人）。但实际上也很好想，因为：

  1. 暴力扩展次数有限：r 只能被扩展 n 次。
  2. 非暴力扩展复杂度低：只有 O(1) 的复杂度。

所以，总的复杂度是 O(n)+O(n)=O(n) 的。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1.1e7 + 5;

int n, res;
int rad[2 * N];
char s[2 * N], c;

void read() {
    s[0] = 'B';
    while (cin >> c) s[++n] = 'A', s[++n] = c;
    s[++n] = 'A';
}

int main() {
    read();
    int mid = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        int j = 2 * mid - i;
        if (r < i) rad[i] = 1;
        else rad[i] = min(rad[j], r - i + 1);
        while (s[i - rad[i]] == s[i + rad[i]]) rad[i]++;
        res = max(res, rad[i] - 1);
        if (i + rad[i] - 1 > r) {
            r = i + rad[i] - 1;
            mid = i;
        }
    }
    cout << res;
    return 0;
}