manacher算法的由来不再赘述，自行百度QWQ。。。
进入正题，manacher算法是一个高效的计算回文串的算法，回文串如果不知道可以给出一个例子：“ noon ”，这样应该就很清晰了；
其实这个算法虽然名字长，但是实际代码很短，而且理解起来并不难。。。（连我这种蒟蒻都懂了）
这里给出模板题
题目描述
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
字符串长度为n
输入格式
一行小写英文字符a,b,c...y,z组成的字符串S
输出格式
一个整数表示答案
其中n的范围为11000000，很显然，只能是O（n）的复杂度，但是为何复杂度这么优秀，这里在讲完算法之后会简述。
定理：
- 一个回文串只有一个对称中心，这个中心上可能有字母或者没有（如果没有字母，我们可以再加上一个，再后面会解释），我们暂且定义其为mid；
- mid两端的区间对称，两边全等（回文串的定义）；
- 如果一个大的回文串一端的区间中有回文串，我们先定义它的中心为 i ，那么大回文串的另一端一定会有相同的回文串；
- 根据上一条，如果我们要更新在右端区间的回文串，那么在左边的回文串半径就可以更新右边的，但是有大回文串的区间限制，所以应当两者取min；
- 结束上面定理的继承之后，直接暴力枚举检查是否两端更新。
解释：
上面的原理毕竟太过干，只是纯理论，所以制图说明；
比如说这个区间是一个大回文串，我们我们用r保留其有边界，那么l就可以根据中点坐标公式变形得到mid*2 - r，所以我们只保留右边界 r 即可。
那么可以看见，如果我们以 i 为这段区间中一个回文串的中心，那么，与它对称的回文串中心就可以求出（根据中点公式，得2*mid - i ，与上面相同）；
那么我们就可以根据定理来继承左边回文串的半径，但是如果左边这个回文串有超过区间的部分怎么办？
这里就用到我们所说的取min了，将左边回文串半径和r - i相比取min，这里就得到了 i 的一个半径，但这个半径一定小于或等于真实半径，所以还需暴力枚举；
这里就可见manachar算法的核心操作了，就是枚举回文串中心，然后继承半径以来减少枚举的次数；
我们用p[ i ]表示以点 i 为中心的回文串的半径，r记录回文串到达的最右边的坐标，mid随之更新，记录这个回文串的中心；
Code
#include<bits/stdc++.h> #define maxn 22000007 using namespace std; char dat[maxn]; int p[maxn],r,cnt=1,mid,ans; void scan(){ char s=getchar(); dat[0]='~';//为了不超出边界的小操作 dat[1]='|';//这个间隔解决了对称中心没有字母的情况 while(s>='a'&&s<='z'){ dat[++cnt]=s; dat[++cnt]='|'; s=getchar(); }//其实与读入优化没差啦 }//自定义读入 int main(){ scan(); for(int i=2;i<=cnt;i++){ if(r>i) p[i]=min(p[2*mid-i],r-i);//由对称的回文串继承，用r-i限制 else p[i]=1;//CASE ：无法继承 while(dat[i-p[i]]==dat[i+p[i]]) p[i]++;//暴力更新 if(p[i]+i>r) r=p[i]+i,mid=i;// r边界必须是最右 ans=max(ans,p[i]);//更新答案 } printf("%d ",ans-1);//这个减一可以自己模拟一下，数学推了话好麻烦的说 }
这就是manachar算法的简述了，当然这里解释一下为什么复杂度为O（n）：
我感觉这和KMP复杂度有些类似，因为这里因为继承的缘故，所以每个点更新次数较少，然后均摊到每个循环，那么复杂度就变成了O（n）了；