众所周知，manacher 又叫“马拉车”算法，是一种线性求解最长回文子串的算法。
推荐结合模板阅读此文。
求最长回文子串，首先想到的是暴力。枚举子串的左右端点 \(l,r\) ，再判断这个子串是否回文。总复杂度 \(O(n^3)\)，效率过低。
观察发现，我们可以只枚举中点，然后同时向左右不断扩展，当无法再扩展时更新答案。
具体来说，我们求出所有的 \(P_i\)，即以字符 \(S_i\) 为中心的最大扩展长度（包括 \(S_i\) 本身）。一开始，所有 \(P_i\) 设为 \(1\)（单个字符肯定是回文串）。
但这样有一个问题：长度为偶数的回文串没有回文中心。针对这个问题，我们在字符串每个字符间加上一个“特殊字符”，保证这个字符不在原字符串的字符集中（下文取 | 作为这个特殊字符）。
拿样例 aaa 举例，加上特殊字符后整个字符串变成了这个样子：
|a|a|a|
这有什么好处呢？对于回文长度为偶数的子串，回文中心就为一个 |。
所以整个串的 \(P\) 数组如下：
S: | a | a | a |
P: 1 2 3 4 3 2 1
可以推出，以 \(S_i\) 为回文中心在新字符串的最长回文串的长度为 \(P_i \times 2 - 1\)。去除特殊字符（显然特殊字符比原字符多一个，所以特殊字符的个数为 \(P_i\)），那么最长回文子串的长度即为 \(P_i - 1\)。
所以答案为 \(\max\{P_i - 1\}\)。
#include<bits/stdc++.h>
using namespace std;
const int N = 11e6 + 9;
char s[N << 1];
int p[N << 1],len,ans;
void read(){//读入字符串
char c = getchar();len = 1;
s[len] = '|';
while(c < 'a' || c > 'z')
c = getchar();
while(c >= 'a' && c <= 'z'){
s[++len] = c;
s[++len] = '|';//添加特殊字符
c = getchar();
}
}
int main(){
read();
for(int i = 1,mx = 0,id = 0;i <= len;i++){
p[i] = 1;
while(s[i - p[i]] == s[i + p[i]])//暴力扩展
p[i]++;
ans = max(ans,p[i] - 1);//更新答案
}
printf("%d",ans);
return 0;
}
但是这样还不是最终的 manacher 算法，我们如果想要得到一个线性算法，就要想如何线性求出 \(P_i\)。
我们记在分别以前 \(i\) 个字符为回文中心扩展后访问到的最右侧的下标为 \(mx\)，即 \(mx = \max\{i + P_i - 1\}\)（以 \(i\) 为扩展中心扩展的长度为 \(P_i\)，那么能访问到的最右侧就是 \(i + P_i - 1\)），同时记取到最大值的 \(i\) 为 \(id\)（如果有多个取最右边的一个）。那么在扩展下一个字符 \(s_{i + 1}\) 时，如果 \(i + 1 \leq mx\)，则 \(s_{i + 1}\) 一定被包含在以 \(id\) 为中心的最长回文串中，那么 \(s_{i + 1}\) 一定在这个回文串中有对称的字符。
接下来我们推一下以 \(id\) 为对称中心，\(i\)（不是 \(i + 1\)）的对称点的下标：
设这个下标为 \(j\)，则 \(j\) 到 \(id\) 的距离和 \(id\) 到 \(i\) 的距离应该相等，即 \(id - j + 1 = i - id + 1\)，整理即得 \(j = 2 \times id - i\)。
所以如果对称点 \(j\) 有一些回文串包含在以 \(id\) 为回文中心的最长回文串中，则其中最大者的长度为 \(\min\{P_j,\text{以} id \text{为对称中心的最长回文串的} \large{\text{左边界}} \text{\normalsize{到}} j \text{\normalsize{的长度}}\}\)（记为 \(len\)），易知 \(len\) 等于 \(i\) 到这个回文串右边界 \(mx\) 的长度（由对称可知），所以 \(len = \min\{P_j,mx - i + 1\}\)这是为了保证以 \(j\) 为回文中心的这个串一定在以 \(id\) 为中心的最长回文串中，这样对称过去才能保证以 \(i\) 为回文中心，上面这个数值扩展长度一定是一个回文串。
由上述我们可以得到如果 \(i\) 包含在以 \(id\) 为中心的最长回文串中，则 \(P_i\) 至少为 \(\min\{P_j,mx - i + 1\}\)，我们再以这个基础暴力扩展。否则，我们就只能老老实实的从 \(P_i = 1\) 开始扩展。
扩展完成之后，我们再按 \(mx\) 和 \(id\) 的定义更新 \(mx\) 和 \(id\) 即可。
总复杂度是线性的（不想证了）。
#include<bits/stdc++.h>
using namespace std;
const int N = 11e6 + 9;
char s[N << 1];
int p[N << 1],len,ans;
void read(){
char c = getchar();len = 1;
s[0] = '~';s[len] = '|';
while(c < 'a' || c > 'z')
c = getchar();
while(c >= 'a' && c <= 'z'){
s[++len] = c;
s[++len] = '|';//添加特殊字符
c = getchar();
}
}
int main(){
read();
for(int i = 1,mx = 0,id = 0;i <= len;i++){
p[i] = i <= mx ? min(p[(id << 1) - i/*i关于id的对称点*/],mx - i + 1) : 1;
while(s[i - p[i]] == s[i + p[i]])//暴力扩展
++p[i];
if(p[i] + i - 1 >= mx){//访问到的最右侧的下标大于mx，更新mx和id
mx = p[i] + i - 1;
id = i;
}
ans = max(ans,p[i] - 1);//更新答案
}
printf("%d",ans);
return 0;
}