正解:$manacher$

解题报告:

传送门$QwQ$

考虑这个操作的实质是啥$QwQ$?其实就,变成以最后一个节点为回文中心的回文子串嘛$QwQ$.显然就先跑个马拉车再说呗$QwQ$.

然后接着考虑,最容易考虑到的是操作一次后长度大于等于$|S|$的,就只需这个位置的回文半径已经顶着右边界了.

然后对于要操作多次的,仔细思考下发现,只需要回文半径顶着左边界且操作一次之后的位置可行就行

然后就做完了$QwQ$

#include
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=1e6+10;
int p[N<<1],len;
bool f[N<<1];
char str[N<<1];

il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il void manacher() { str[0]='*';str[len=1]='|';rc ch=gc;while(ch<'a' || ch>'z')ch=gc;
while(ch<='z' && ch>='a')str[++len]=ch,str[++len]='|',ch=gc;;str[++len]='#';
for(ri i=1,mx=0,mid=0;i<=len;++i) { if(mx>=i)p[i]=min(mx-i+1,p[(mid<<1)-i]); while(str[i-p[i]]==str[i+p[i]])++p[i];;if(i+p[i]-1>mx)mx=i+p[i]-1,mid=i;
}
}

int main()
{
freopen("5446.in","r",stdin);freopen("5446.out","w",stdout);
ri T=read();
while(T--)
{
memset(f,0,sizeof(f));memset(p,0,sizeof(p));manacher();
//rp(i,1,len-1)printf("%c",str[i]);;printf("\n");
//rp(i,1,len-1)if(!(i&1))printf(" %d",p[i]);;printf("\n");
//rp(i,1,len-1)if(!(i&1))printf(" %d",i>>1);;printf("\n");
my(i,len,2){if(i+p[i]==len || (i-p[i]+1==1 && f[i+p[i]-2]))f[i]=1;}
for(ri i=2;i>1);;printf("\n");
}
return 0;
}