#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
int n,p[maxn],s[maxn],s_new[maxn];
int init(){
s_new[0]=-
2,s_new[
1]=-
1;
int j=
2;
for(
int i=
0;i<n;i++
){
s_new[j++]=
s[i];
s_new[j++]=-
1;
}
return j-
1;
}
int manacher(){
int len=
init();
int mx=
0,id,res=
0;
for(
int i=
0;i<len;i++
){
if(i<mx)p[i]=min(mx-i,p[
2*id-
i]);
else p[i]=
1;
while(s_new[i-p[i]]==s_new[i+p[i]] && s_new[i-p[i]]<=s_new[i-p[i]+
2])
p[i]++
;
if(i+p[i]>
mx)
mx=i+p[i],id=
i;
res=max(res,p[i]-
1);
}
return res;
}
int main(){
int t;
cin>>t;
while(t--
){
cin>>
n;
for(
int i=
0;i<n;i++)scanf(
"%s",&
s[i]);
memset(p,0,
sizeof p);
cout<<manacher()<<
'\n';
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10784323.html
