Manacher，O(n)求字符串最长回文子串的良心算法
首先，求最长回文字串的两个个方法，第一个是将所有字串列出来然后逐个判断，时间复杂度高达O(n3)，这里不多赘述，然后就是选择一个字符，向两边扩展，判断是否相等，相等则长度自增。时间复杂度高达O(n2)
然后就是可以用hash来判断回文，时间复杂度为O(nlogn)，多数也能过，但是让你写马拉车的题除外——
咳，废话少说，学马拉车之前要明确一个性质
1.如果一个字符串回文，则它有一个回文中心
2.关于回文中心对称的两个回文子串相等
3.则可以得出一个大回文串中某个点的回文半径（即回文串的长度/2上取整）等于和它关于 大回文串回文中心 对称的点的回文半径相等，因为对称的两点再大回文串内的两边都拥有同样的东西
4.所以就可以用之前算过的来更新大回文串右半边的点，，，但是在进行下一步之前，是应该进行依托拓展的，拓展方法参照O(n^2)思路
5.然后就是对于回文串超过了大回文串的右端点的情况，更新大回文串的右端点，然后继续重复上述操作...
再就是一些细节的处理——emm好像manacher这种东西也没有太多的细节。。。
好的，接下来就放一道板子（你知道对于依托没怎么切过蓝题的孩子来说，点开一个算法全是蓝紫的感觉咩）
Manacher纯板子
6.哦对了，发现有一个东西忘讲了，就是奇回文串和偶回文串的判断方式的差别，如果在两个字符中间放一个‘#’，就可以使偶回文串变成奇回文串，比如aa变成#a#a#
接下来就是代码——
点击查看代码
#include<bits/stdc++.h>
using namespace std;
string s1,ss;
const int N=2.4e7+10;
int n,d[N];
namespace Cathy
{
inline void rebuild()
{
int k=0;
ss+="$#";
k=1;
for(int i=1;i<=n;i++)
{
ss+=s1[i-1];
ss+='#';
k+=2;
}
n=k;
}
inline void work()
{
d[1]=1;
for(int i=2,l,r=0;i<=n;i++)
{
if(i<=r)
{
d[i]=min(d[r-i+l],r-i+1);
}
while(ss[i-d[i]]==ss[i+d[i]])
{
d[i]++;
}
if(i+d[i]-1>r)
{
r=i+d[i]-1;
l=i-d[i]+1;
}
}
}
inline void Main()
{
cin>>s1;
n=s1.size();
rebuild();
work();
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,d[i]);
}
cout<<ans-1<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Cathy::Main();
return 0;
}