manacher

算法流程
我们要计算\(i+k\)这个点的回文串，\(i\)这个点是\(i+l[i]\)最大的点，也就是能达到的最远的点
当我们计算\(i+k\)这个点没有在最远到达点之前，暴力扩展
被包含的话，分情况讨论
①
i-k 回文串有一部分在 i 的回文串之外
这种情况p[i+k]=p[i]-k
这时候就有人会有疑惑了,p[i-k]那里的长度比你上面上的p[i]-k要长呀 ?
很正确虽然p[i-k]的长度长，但是p[i]的延伸最终在那里终止了
就说明i+p[i]和i-p[i]是不相同的两个符号,所以p[i+k]的长度最多只是p[i]-k
②
i-k的回文串全部在p[i]之内,所以p[i+k]=p[i-k]
那么这时的p[i+k]会不会更长呢,不可能
③
i-k的右端和i的右端重合,这时候 p[i+k]最小是p[i]-k;并且
可能继续增加
-----出自57级shenben学长

#include <iostream>
#include <cstring>
#include <algorithm> 
#include <cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=11000007;
char S[maxn<<1],s[maxn];
int n,l[maxn<<1];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    int i=0,len=1;
    S[0]='@';S[1]='#';
    while(i<=n) S[++len]=s[++i],S[++len]='#'; 
    int ma=0,id=0,ans=0;
    FOR(i,1,len) {
        if(ma > i) l[i]=min(ma-i,l[id*2-i]);
        else l[i]=1;
        while(S[i+l[i]]==S[i-l[i]]) l[i]++;
        if(ma < i+l[i]-1) id=i,ma=i+l[i]-1;
        ans=max(ans,l[i]-1);
    }
    cout<<ans<<"\n";
    return 0;
}