最长回文字串（马拉车算法）

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Min(a,b) a>b?b:a  
#define Max(a,b) a>b?a:b
using namespace std;
typedef long long ll;
int read() {
    int x=0; int f=1;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) f=-1; ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}
const int maxn=3e6+100;
const int mod=1e9+7;
int len[maxn];
char str[maxn];
char ss[maxn];
int n,mx,id,len1;
void inint(){
    int k=0;
    str[k++]=‘$‘;
    for(int i=0;i<len1;i++){
        str[k++]=‘#‘;
        str[k++]=ss[i];
    }
    str[k++]=‘#‘;
    len1=k;
}
int Manacher(){
    len[0]=0;
    int sum=0;
    mx=0;
    for(int i=1;i<len1;i++){
        if(i<mx) len[i]=min(mx-i,len[2*id-i]);
        else len[i]=1;
        while(str[i-len[i]]==str[i+len[i]]) len[i]++;
        if(len[i]+i>mx){
            mx=len[i]+i;
            id=i;
            sum=max(sum,len[i]);
        }
    }
    return (sum-1);
} 
int main(){
    scanf("%d",&n);
    while(n--){
        memset(str,0,sizeof(str));
        scanf("%s",ss);
        len1= strlen(ss);
        inint();
        int t=Manacher();
        printf("%d\n",t); 
    }
}