1 // Luogu P3805 【模板】manacher 算法
2 #include <iostream>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 const int N=3e7;
8 char a[N],s[N];
9 int d[N]; //回文半径函数
10
11 void get_d(char*s,int n){
12 d[1]=1;
13 for(int i=2,l,r=1;i<=n;i++){
14 if(i<=r)d[i]=min(d[r-i+l],r-i+1);
15 while(s[i-d[i]]==s[i+d[i]])d[i]++;
16 if(i+d[i]-1>r)l=i-d[i]+1,r=i+d[i]-1;
17 // printf("i=%d d=%d [%d %d]\n",i,d[i],l,r);
18 }
19 }
20 int main(){
21 //改造串
22 scanf("%s",a+1);
23 int n=strlen(a+1),k=0;
24 s[0]='$',s[++k]='#';
25 for(int i=1;i<=n;i++)
26 s[++k]=a[i],s[++k]='#';
27 n=k;
28
29 get_d(s,n);//计算d函数
30 int ans=0;
31 for(int i=1;i<=n;i++)
32 ans=max(ans,d[i]);
33 printf("%d\n",ans-1);
34 return 0;
35 }
练习：
P3501 [POI2010] ANT-Antisymmetry - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签：int,Luogu,char,算法,P3805,include,拉车 From： https://www.cnblogs.com/rw666/p/18073240