Copyright By

注意事项

讲评人没有实力，也没有烤鸭皮皮，所以对于接下来提到的一些结论将不予证明，感兴趣的可以自己bdfs一下，或者课后询问讲评人

部分定义不准确，并不形式化，是讲评人自己思考后的结果

如果觉得自己的想法与讲评人有不同或者算法更优，可提出自己的见解

---

算法用途

Manacher可求解回文串类问题（定义将稍后给出）

算法的结果是一个数组d，其中$d[i]$表示以第i个字符为中心的回文半径

时空复杂度$O(n)$

定义

子串 原串中连续的一部分，形如$s[l...r]$的字符串 原串的子串数为$O(n)$

回文串 一个倒过来与原串相同的字符串

根据字符串长度分为奇回文串、偶回文串

回文子串 顾名思义，一个字符串的子串若是回文串就是它的回文子串

回文半径 这里只讨论奇回文子串的回文半径

以$s[i]$为中心的最长回文子串的最大长度加一的一半即为$s[i]$的回文半径

Manacher处理的就是字符串每一位的回文半径，所以需要把偶回文串预处理为奇回文串

---

好的那么现在开始讲算法啦~

---

预处理

现在有一个字符串aabaaa

很容易看出aa、aba等都是该串的回文子串

为了处理偶回文串，我们把字符串见的每两位间插上一个原串中没有的字符，就像这样：

#a#a#b#a#a#a#

这样偶回文子串就会变成类似a#a，以#为中心的奇回文子串

而原本的奇回文子串会变成类似a#b#a，以字符串中字符为中心的奇回文子串

最后在边界上加两个未出现且不相等的字符，如下：

@#a#a#b#a#a#a#&

这样在匹配到边界字符时就会跳出循环，便不用考虑边界问题了

原串的最大回文子串长度=新串的最大回文半径-1

代码如下：

inline void Init() {
    scanf("%s", s1 + 1);
    int len = strlen(s1 + 1);

    //构建新串
    n = 0;
    s[++n] = '#';
    for (int i = 1; i <= len; i++) {
        s[++n] = s1[i];
        s[++n] = '#';
    }
    s[0] = '@';
    s[n + 1] = '&';
}

算法本体

算法用到了一种名叫做加速盒子的技术

具体来说：

对于一个回文串内部一定是左右对称的，那么在它内部的回文半径一定是左右对称的，我们只需用对称的已经算出的$d[j]$来更新新的$d[i]$，再尽可能地扩展即可

那么加速盒子便是右端点最大的一个回文串

首先用l,r变量维护加速盒子左右边界

容易得到$d[1]=1$

接下来，如果i在加速盒子内，即$i\leq r$，就直接用i在加速盒子中的对称点，即$d[r-i+l]$更新$d[i]$即可

注意：若回文子串超出盒子要暴力

接着尝试更新加速盒子

接着暴力尝试扩展即可

代码如下：

inline void Manacher() {
    d[1] = 1;
    int l = 1, r = 1;
    for (int i = 2; i <= n; i++) {
        if (i <= r) d[i] = min(d[r - i + l], r - i + 1);
        while (s[i - d[i]] == s[i + d[i]]) d[i]++;
        if (i + d[i] - 1 > r) {
            l = i - d[i] + 1;
            r = i + d[i] - 1;
        }
    }
}

---

最后的最后，贴出一份求解原串最长回文子串长度的代码 洛谷P3805 Manacher模板

#include<bits/stdc++.h>

using namespace std;

static constexpr int AwA = 1.1e7 + 10;

char s[AwA << 1], s1[AwA];
//新串长度为原串长度的2倍加一
int d[AwA << 1];
//回文半径
int n;

inline void Init() {
    scanf("%s", s1 + 1);
    int len = strlen(s1 + 1);

    //构建新串
    n = 0;
    s[++n] = '#';
    for (int i = 1; i <= len; i++) {
        s[++n] = s1[i];
        s[++n] = '#';
    }
    s[0] = '@';
    s[n + 1] = '&';
}

inline void Manacher() {
    d[1] = 1;
    int l = 1, r = 1;
    for (int i = 2; i <= n; i++) {
        if (i <= r) d[i] = min(d[r - i + l], r - i + 1);
        while (s[i - d[i]] == s[i + d[i]]) d[i]++;
        if (i + d[i] - 1 > r) {
            l = i - d[i] + 1;
            r = i + d[i] - 1;
        }
    }
}

int main() {
    Init();
    Manacher();

    int ans = 1;
    for (int i = 1; i <= n; i++) ans = max(ans, d[i] - 1);
    printf("%d\n", ans);

    return 0;
}

完结撒花