Manacher
参考：Manacher
模板题：P3805 【模板】manacher算法
用于求最长回文串，复杂度为\(O(n)\)，其中d1[i]表示以 i 为中心的长度为奇数的回文子串，如aaa中，d1[0]=1,d1[1]=2，d2[i]表示以 i 为右中心的长度为偶数的回文子串，如baab中，d2[1]=0,d2[2]=2
马拉车算法的关键在于利用回文串的对称性减少了重复计算。
const int maxn=1e7+1e6+5;
int d1[maxn],d2[maxn]; //d1保存奇数回文串，d2保存偶数回文串
void manacher(string &s){
//回文串的长为 2*d1[i]-1,2*d2[i]
int n=s.size();
for(int i=0,l=0,r=-1;i<n;++i){
int k=(i>r)?1:min(d1[l+r-i],r-i);
while(0<=i-k&&i+k<n&&s[i-k]==s[i+k])
k++;
d1[i]=k--;
if(i+k>r)
l=i-k,r=i+k;
}
for(int i=0,l=0,r=-1;i<n;++i){
int k=(i>r)?0:min(d2[l+r-i+1],r-i+1);
while(0<=i-k-1&&i+k<n&&s[i-k-1]==s[i+k])
k++;
d2[i]=k--;
if(i+k>r)
l=i-k-1,r=i+k;
}
}
CAD加油！欢迎跟我一起讨论学习算法
