manacher
马拉车算法（ ，OI-Wiki
算法介绍： 线性复杂度内找出以每个字符为回文中心的最长回文半径
存下模板代码：
int l = 0, r = -1;
for(int i=1; i<=n; i++){
int k = i > r ? 1 : min(d[l+r-i], r-i+1);
while(i - k > 0 and k + i <= n and s[i-k] == s[i+k]) k++;
d[i] = k--;
if(r < i + k) l = i - k , r = i + k;
}
板子题： 【模板】manacher
code
d ```cpp #includeinline ll read(){
char c=getchar(); ll x=0, f=1;
while(!isdigit(c)) (c=='-'?f=-1:f=1), c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar();
return x*f;
}
const int N = 2.2e7 + 10;
int n, d[N];
char in[N], s[N];
signed main(){ // a
// Aqrfre(a, a);
cin>>(in+1); n = strlen(in+1);
int cnt = 0;
for(int i=1; i<=n; i++)
s[++cnt] = '@', s[++cnt] = in[i];
s[++cnt] = '@'; n = cnt;
int l = 0, r = -1, ans = 0;
for(int i=1; i<=n; i++){
int k = i > r ? 1 : min(d[l+r-i], r-i+1);
while(i - k > 0 and k + i <= n and s[i-k] == s[i+k]) k++;
d[i] = k--;
if(r < i + k) l = i - k , r = i + k;
}
for(int i=1; i<=n; i++){
if(s[i] == '@') ans = max(ans, d[i] / 2 * 2);
else ans = max(ans, d[i] - !(d[i] & 1));
}
cout<<ans<<"\n";
return 0;
}
</details>