1.Manacher马拉车算法介绍

Manacher算法，又称马拉车算法。用于计算字符串每一个位置为对称中心的回文串长度，即可以用来查询一个长度为nn的最长回文字串。他的时间复杂度是O(n)O(n)。是该情景中效率最高的（你不遍历整个字符串咋求出来）

回文串就是从头读到尾部和从尾部读到头都一样的字符串，例如“abbba”。一个回文串是镜像对称的，也就是说他反转之后也是和原串相同的，我们就是依靠这个性质来跑出马拉车算法的。

回文串有两种，一种是奇数的串，就是字符个数有奇数个。一种是偶数的串，例如“abba”就是一个。对于奇数的传，我们可以发现他的对称中心就是中间的‘b’，但是偶数的串呢。他就有2个对称中心，一个是第二个字符‘b’，一个是第三个字符‘b’（门前有两颗树，一颗是B树，另一个也是B树）

总之偶数的回文串对称中心有2个。

2.暴力法求解

不是说讲马拉车吗？怎么先给我讲暴力法啦？

其实马拉车就是暴力法的改进。所以我们先讲讲暴力法如何求解。

我会枚举！，每次选一个点让后判断是不是回文串！
O(n3)O(n^3)

我会优化！我们考虑到上述加粗的，一个回文串是镜像对称的，也就是说我们可以枚举中心，让后向左右两边拓展。例如以“abc”来说，以b为中心，a≠ca\ne c，所以直接结束！

时间复杂度O(n2)O(n^2)

写起来差不多就是核心这个循环，其中p[i]p[i]表示回文半径

1
2
3
while (s[i+p[i]+1]==s[i-p[i]-1]){//+1和-1是向外拓展一格
	p[i]++;
}

我们仔细思考一下为什么效率低，可以发现我们每次枚举端点都会扫一遍字符串，在最坏的情况下这个字符串里面有许多的回文串，而且都很长，效率近乎降至O(n2)O(n^2)，所以马拉车就是利用上面镜像的性质，减少了重复检查。

3.马拉车算法核心

这里引用Lstdo的博客图

首先我们设maxlmaxl和maxrmaxr跟别表示目前找到的回文串左端点最左的位置和右端点最右的位置，pospos表示这个回文串的对称中心。

回到回文串，回文串的性质是镜像对称，也就是我们可以得出一个重要的性质回文的镜像也是回文。

例如上图，如果jj处有一个回文字串，黄色部分完全一致，那么对称过去ii处也就肯定有一个回文字串。我们可以很简单的求出来jj的位置就是pos⋅2−ipos\cdot 2-i的，也就是说我们可以直接把p[j]p[j]的值赋给p[i]p[i]…吗？

处理时，问题并没有那么的简单，这里我们将一一列举。

  1. 最普通的情况，这种情况就是上面的情况，我们就直接赋值即可。
  2. 如下，如果发现我们直接赋值的话，那么肯定会超过maxrmaxr

    那就不能直接赋值，这个时候我们要尽可能缩在区间内，所以我们要和j−maxlj-maxl和maxr−imaxr-i取minmin。
  3. 当ii在右端点的后面

    这没办法啦，只能暴力扩展啦。

综上：

  1. 如果i<maxri<maxr,就更新pip_i
  2. 暴力拓展
  3. 更新maxrmaxr和pospos
    这就是马拉车，十分甚至九分的简单

等会！你这个我数了（不是哥们），是奇数串！那如果是偶数串呢？

我们不得不说这确实是一个问题，中心为一个字符或两个编码十分的麻烦。我们这里运用一个小技巧，就是在SS的每一个字符左右插入一个不属于SS的字符，比如说’#'，把“abcba”变成“#a#b#c#b#a#”，中心字符还是c，如果是偶数串，那么“abba”变为“#a#b#b#a#”唉这不就变成奇数串，中心就是两个b中间夹的“#”。但是还有一个问题，会越界啊。这个时候我们可以在开头和结尾各加上2个不同的字符，比如说“$”和“&”，这样就变成了 ” $#a#b#c#b#a#& “在暴力拓展的时候就不会越界了。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// TODO：学麻辣烫车
#include<iostream>
#include<cstring>
using namespace std;
const int MN=1.1*1e7+15;
string s1,s;
int p[MN*2];//这里一定要开2倍！
void change(){//直接用pushback怎么说，stl的魅力
    s.push_back('$');
    s.push_back('#');
    for(int i=0;i<s1.length();i++){
        s.push_back(s1[i]);
        s.push_back('#');
    }
    s.push_back('&');
}
void manacher(){
    int r=0,c;
    for(int i=1;i<s.length();i++){
        if(i<r){//将两种情况合并
            p[i]=min(p[c*2-i],p[c]+c-i);
        }
        while (s[i+p[i]+1]==s[i-p[i]-1])
        {//暴力扩展，注意加一和减一是向外拓展
            p[i]++;
        }
        if(p[i]+i>r){//如果超范围啦，直接就更新r和c变为当前节点的回文串
            r=p[i]+i;
            c=i;
        }
    }
}
int main(){
    cin>>s1;
    change();
    // cout<<s<<endl;
    manacher();
    int ans=0;
    for(int i=0;i<s.length();i++){
        ans=max(ans,p[i]);
    }
    // for(int i=0;i<s.length();i++){
    //     cout<<p[i]<<" ";
    // }
    // cout<<endl;
    cout<<ans;
    return 0;
}