问题引入
给定一个长度为 \(n\) 的字符串 \(s\)，保证 \(s\) 只由小写字母组成，要求计算出 \(s\) 中最长的连续回文子串的长度。
乍一看，诶我会 \(O(n^3)\) 做法！枚举左右端点然后暴力判断就行。
但是这也太慢了吧！我左思右想，那就固定一个中心点（这里的中心点不仅可以是一个字符，也可以是两个相邻字符之间空格那个位置，这样便涵盖了偶数回文串和奇数回文串两种情况），然后双指针左右两边扩展吧！这样我就可以实现 \(O(n^2)\) 了！
接着我们发现，可以对上面那个算法进行二分优化！至于快速判断两个串是否相等，或者说是否相互匹配嘛……可以用 Hash！这样我们就有一个 \(O(n \log n)\) 的算法了！
但是，这个算法带个 \(\log\)，还不算很优，并且 Hash 是有冲突概率的，正确性无法百分百保证……有没有更加优秀的算法呢？
什么是 Manacher？
刚才提到的那个问题，我们利用现有知识成功构造出一个 \(O(n \log n)\) 的 Hash 加二分的算法。嗯，这个算法好像很不错，但是有没有更优的呢？有的兄弟有的，比如这边这个 Manacher 算法，可以在严格线性 \(O(n)\) 的时间复杂度内搞定这个问题，正确性也当然是百分百的啦！
好了好了来系统介绍一下 Manacher。
Manacher，也称马拉车，虽然它和马拉车一点关系都没有，因为这名儿是英译过来的，其能够在严格线性的时间复杂度内求出字符串中所有回文子串的数量和长度，是一个非常好用的字符串算法。说它是字符串算法，其实放到数组上也照常能用吧？
但是这些定义什么的都不是重点，重点是这个 Manacher 究竟该怎么去做。
如何实现 Manacher？
还记得之前提到的那个 \(O(n^2)\) 的算法吗？固定中心点然后扩展……这其实是 Manacher 的弱化版。你可以理解为，Manacher 就是给这东西加了些奇奇妙妙的剪枝，把它的速度硬生生从 \(O(n^2)\) 拉到了 \(O(n)\)。
那么 Manacher 肯定也是固定中心点了。上面提到过中心点可能是字符之间的空隙，这玩意儿好像不好整啊，怎么办？考虑用一个简单粗暴的方法，将这个字符串改造一下，相邻两个字符之间插一个无意义字符如 #，然后再去求就可以了，最后答案的记录与输出那部分稍微改改就好。
既然是固定中心点，那我们就枚举这个中心点 \(i\)，从 \(1\) 到 \(n\)。这里的 \(n\) 默认为插过无意义字符后的字符串长度了哈，并且我们的字符串是从 \(1\) 开始编号的。
为了方便，这里记录 \(p_i\) 表示以 \(i\) 为中心点的最长回文子串一半的长度，也就是只算自己和左边一部分。
求解的时候，最粗暴的办法就是直接进行左右扩展，这也是之前提到过的方法。但是我们会发现一个事情，如果当前 \(i\) 这个位置被包含在一个之前求过的大的子回文串里面（你不需要在意这里的中心点具体在哪里，只要是之前求过的就行），那么这个 \(p_i\) 其实根本没这么麻烦，让它等于 \(i\) 在这个之前求过的大的回文子串里相对应的那个位置如 \(j\) 的答案 \(p_j\) 就可以了。
手推一下，这个东西似乎是对的，但好像又有些漏洞。漏洞在哪里呢？你要想啊，当前这个 \(i\) 对应到了前面的一个 \(j\)，这个 \(p_j\) 扩展到的范围没出这个大的子回文串倒还好啊，要是出去了，\(i\) 右边可没有 \(j\) 左边那些扩展出去了的字符啊！那么这里肯定就不能直接赋值过来了，会错，因此这里的赋值还要和 \(i\) 在这个大的子回文串里面能扩展的最长长度取个 \(\min\)。
这样就结束了吗？没，毕竟 \(i\) 可能还有扩展的空间，而且要是 \(i\) 没被包含在之前求过的大的子回文串里面，那你就求都还没开始求啊！别急，做完刚才一步“剪枝”，就可以放心大胆继续扩展了，左右扩展，只要还有位置并且字符匹配的上，咱就一直扩展下去。扩展完了，这个答案才是你真正的答案。
Manacher 的过程基本到这里就结束了，不过还有一个问题，那就是如何判断 \(i\) 这个位置有没有被包含在一个之前求过的大的子回文串里面。肯定不能又暴力回退回去啊，但是我们可以用变量 \(l\) 和 \(r\) 记录一下，以 \(r\) 的大小为第一关键字。怎么说？就是，只要现在某个新的 \(i\) 出来了一个新的 \(p_i\) 值，就算出它所对应的右端点，和现有的 \(r\) 比一比，如果比现有的 \(r\) 大，咱就直接把 \(l\) 和 \(r\) 都换成新的；否则就不需要更换了，保留旧值就好。
这样的时间复杂度真的是严格线性 \(O(n)\) 的吗？看起来还是 \(O(n^2)\) 啊！其实不然，加上这个所谓“剪枝”之后，就有很多 \(i\) 是扩展不出去的，直接 \(O(1)\) 了。而这个 \(l\) 和 \(r\) 最多也只能把整个 \(n\) 遍历一趟，之后就走不动了，所以这里总的加起来也只有 \(O(n)\)，虽然中途可能一次就跑 \(O(n)\)。所以时间复杂度确实是严格线性 \(O(n)\) 的。
这就是 Manacher，它比较好理解，而且代码量很小呢！
Manacher 板题代码
这个纯板子，就和上面“问题引入”部分所提到的问题是一样的，因此就是一个 Manacher 的模版就可以啦。
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 2.5e7+5;
int n,p[N],Ans;string t,s;
int read(){int su=0,pp=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}return su*pp;
}int main(){cin>>t;s=" ";for(char c:t)s+=c,s+='#';s.pop_back();n=s.size()-1;for(int i=1,l=0,r=-1;i<=n;i++){int len=(i>r?1:min(p[l+r-i],r-i+1));while(i-len>=1&&i+len<=n&&s[i-len]==s[i+len])len++;p[i]=len,Ans=max(Ans,len-(s[i+len-1]=='#'));if(i+len-1>r)l=i-len+1,r=i+len-1;}cout<<Ans<<"\n";return 0;
}