【模板】Manacher 算法 最长回文子串

参考博客：Manacher算法——最长回文子串

Manacher算法的模板，写得比较简洁

作为一个模板，还是不错的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int tst,f[maxn];
char a[maxn],s[maxn];
int Manacher(){
    int n=,res=,maxR=,pos=;
    for (int i=;a[i];i++) s[++n]='#',s[++n]=a[i];s[++n]='#';
    for (int i=;i<=n;i++){
        f[i]=i<maxR?min(f[pos*-i],maxR-i+):;
        while (i-f[i]>&&i+f[i]<=n&&s[i-f[i]]==s[i+f[i]]) f[i]++;
        if (i+f[i]->maxR) maxR=i+f[i]-,pos=i;
        res=max(res,f[i]-);
    }
    return res;
}
int main(){
    scanf("%d",&tst);
    for (int i=;i<=tst;i++) scanf("%s",a),printf("%d\n",Manacher());
    return ;
}