题目传送门

---

初学 $ Manacher $ (马拉车)算法

Manacher算法用于处理回文串问题，可以求出每个字符所在的最长回文串的长度

---

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=11000005;
char s[N],sw[2*N];
int r[2*N];
int deal()
{
    int len=strlen(s);
    sw[0]='$';
    sw[1]='#';
    int lon=2;
    for(int i=0;i<len;i++)
    {
        sw[lon++]=s[i];
        sw[lon++]='#';
    }
    sw[lon]='\0';
    return lon;
}
int manacher()
{
    int len=deal();
    int id,mx=0,maxlon=0;
    for(int i=1;i<len;i++)
    {
        if(i>=mx) r[i]=1;
        else r[i]=min(r[2*id-i],mx-i);
        while(sw[i-r[i]]==sw[i+r[i]]) r[i]++;
        if(mx<i+r[i])
        {
            id=i;
            mx=i+r[i];
        }
        maxlon=max(maxlon,r[i]-1);
    }
    return maxlon;
}
int main()
{
    cin>>s;
    printf("%d\n",manacher());
    return 0;
}