字符串（算法竞赛）--Manacher（马拉车）算法
1、B站视频链接：F05 Manacher(马拉车)_哔哩哔哩_bilibili
题目链接：【模板】manacher - 洛谷
#include <bits/stdc++.h>
using namespace std;
const int N=3e7;
char a[N],s[N];
int d[N];//回文半径函数void get_d(char*s,int n){d[1]=1;for(int i=2,l,r=1;i<=n;i++){if(i<=r)d[i]=min(d[r-i+1],r-i+1);//盒内加速while(s[i-d[i]]==s[i+d[i]])d[i]++;//盒外暴力枚举if(i+d[i]-1>r)l=i-d[i]+1,r=i+d[i]-1;//更新盒子 }
}
int main(){//改造串 scanf("%s",a+1);int n=strlen(a+1),k=0;s[0]='$',s[++k]='#';//0为$,1为#for(int i=1;i<=n;i++){s[++k]=a[i],s[++k]='#';}n=k;//最后的长度为kget_d(s,n);int ans=0;for(int i=1;i<=n;i++){ans=max(ans,d[i]);}printf("%d\n",ans-1);//最大半径减一 return 0;
} 