A
发现答案长度不超过 (lceil log_2 n ceil +1)。令 (m=lceil log_2 n ceil +1)，取出原串中所有长为 (m) 的 (01) 串表示成数字，并取这些数的 (mathrm{mex})，即为长度是 (m) 时的答案。
从大到小枚举答案长度 (l)，当枚举到 (l) 时，它的信息可以通过 (l+1) 的信息整体右移一位、再加上末尾的一段、再去重得到。
不断地取 (mathrm{mex}) 即可。时间复杂度为 (O(n+dfrac{n}{2}+dfrac{n}{4}+dots)=O(n))。
const int N=16777220,Inf=0x3f3f3f3f;
int n,buk[N<<1];char s[N];
int main(){
fread(s+1,sizeof(char),N,stdin);
int pos;for(pos=1;s[pos]=='0'||s[pos]=='1';++pos);
s[pos]=' ';
n=pos-1;
int len=1;for(;(1<<len)<=n;++len);
int x=0;For(i,1,len) x=(x<<1)|(s[i]-48);
For(i,len,n){
buk[x]=len;
x=(x<<1)|(s[i+1]-48);
x&=(1<<len)-1;
}
int minlen=Inf,minmex=Inf;
for(;len>=1;--len){
int mex=Inf,st;
#define Unroll(stat) if(buk[stat]!=len){mex=stat;break;}
for(st=0;st+4<=(1<<len)-1;st+=4){
Unroll(st);Unroll(st+1);Unroll(st+2);Unroll(st+3);
}
for(;st<=(1<<len)-1;++st){
Unroll(st);
}
#undef Unroll
#define Unroll(stat) if(buk[stat]==len) buk[(stat)>>1]=len-1;
for(st=0;st+4<=(1<<len)-1;st+=4){
Unroll(st);Unroll(st+1);Unroll(st+2);Unroll(st+3);
}
for(;st<=(1<<len)-1;++st){
Unroll(st);
}
#undef Unroll
if(mex!=Inf) minlen=len,minmex=mex;
x=0;
For(i,n-len+2,n) x=(x<<1)|(s[i]-48);
buk[x]=len-1;
}
string ans;
for(int i=1;i<=minlen;++i,minmex>>=1) ans.push_back((minmex&1)+48);
reverse(ans.begin(),ans.end());
printf("%s
",ans.c_str());
return 0;
}