RT,得分80,TLE了#8#10两个点

#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+10;
void Min(int& x,int y){x=min(x,y);}
void Max(int& x,int y){x=max(x,y);}
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<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
int n;
char s[NR];
int pi[NR];
int getnxt(int x,char ch){
	if(s[x+1]==ch)return x+1;
	return (!x)?0:getnxt(pi[x],ch);
}
string t;
int getnxt2(int x,char ch){
	if(t[x+1]==ch)return x+1;
	return (!x)?0:getnxt2(pi[x],ch);
}
bool check(string ttt,int Len)
{
	t=' '+ttt;int len=t.length()-1;
	for(int i=0;i<=len;i++)pi[i]=0;
	for(int i=2;i<=len;i++)pi[i]=getnxt2(pi[i-1],t[i]);
	if(pi[len]==Len)return 1;
	return 0;
}
string solve(int l,int r)
{
	for(int i=l;i<=r;i++)pi[i]=0;
	for(int i=l+1;i<=r;i++)pi[i]=getnxt(pi[i-1],s[i]);
	if(pi[r]==r-l){
		string S="";
		for(int i=1;i<=r-l+1;i++)S=S+'0';
		return S;
	}
	if(pi[r]==0){
		string S="";
		for(int i=1;i<=r-l;i++)S=S+'0';
		S=S+'1';return S;
	}
	int len=r-l+1-pi[r];
	if(len*2<=r-l+1){
		string tmp=solve(r-len-(r-l+1)%len+1,r);
		string tt="",ans="";
		for(int i=0;i<len;i++)tt=tt+tmp[i];
		int num=(r-l+1)/len;
		for(int i=1;i<=num-1;i++)ans=ans+tt;
		ans=ans+tmp;return ans;
	}
	len=pi[r];
	string tmp=solve(l,l+len-1);
	string _0_="",_01_="";
	for(int i=1;i<=(r-l+1)-len-len;i++)_0_=_0_+'0';
	for(int i=1;i<=(r-l+1)-len-len-1;i++)_01_=_01_+'0';_01_=_01_+'1';
	if(check(tmp+_0_+tmp,len))return tmp+_0_+tmp;
	else return tmp+_01_+tmp;
}
void work()
{
	scanf("%s",s+1),n=strlen(s+1);
	cout<<solve(1,n)<<endl;
}
int main()
{
	int T=read();while(T--)work();
	return 0;
}
/*
1
ABIAB
*/