传送门

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 300

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,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 N=1e6+10;

char s[N],str[N*4];

int p[N*4],len1,len2;

void init()

{

    len1=strlen(s);

    str[0]='(';

    str[1]='#';

    for(int i=0;i<len1;i++)

    {

        str[i*2+2]=s[i];

        str[i*2+3]='#';

    }

    len2=len1*2+2;

    str[len2]=')';

}

void Manacher()

{

    memset(p,0,sizeof(p));

    int id=0,mx=0;

    for(int i=1;i<len2;i++)

    {

        if(mx>i) p[i]=min(mx-i,p[2*id-i]);

        else p[i]=1;

        for(;str[i+p[i]]==str[i-p[i]];p[i]++);

        if(p[i]+i>mx)

        {

            mx=p[i]+i;

            id=i;

        }

    }

}

int main()

{

    int T=read();

    while(T--)

    {

        scanf("%s",s);

        init();

        Manacher();

        int mx=1;

        for(int i=0; i<len2; i++) mx=max(mx,p[i]);

        printf("%d\n",mx-1);

    }

    return 0;

}

点击回到顶部