【题目大意】
给出一个字符串，求出与其循环同构的字符串中，字典序最小的一个。
【题解】
以原字符串的两倍建立自动机，按字典序在parent树上搜索，
得到的第一个长度为n的字符串就是答案。
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=40005;
char s[N];
struct sam{
int p,q,np,nq,cnt,last,a[N][26],l[N],f[N];
sam(){cnt=0;last=++cnt;}
void init(){
cnt=0;last=++cnt;
memset(a,0,sizeof(a));
memset(l,0,sizeof(l));
memset(f,0,sizeof(f));
}
void extend(int c){
p=last;np=last=++cnt;l[np]=l[p]+1;
while(!a[p][c]&&p)a[p][c]=np,p=f[p];
if(!p)f[np]=1;
else{
q=a[p][c];
if(l[p]+1==l[q])f[np]=q;
else{
nq=++cnt;l[nq]=l[p]+1;
memcpy(a[nq],a[q],sizeof(a[q]));
f[nq]=f[q]; f[np]=f[q]=nq;
while(a[p][c]==q)a[p][c]=nq,p=f[p];
}
}
}
void solve(){
init();
scanf("%s",s);
int n=strlen(s),len=n;
for(int k=0;k<2;k++)for(int i=0;i<n;i++)extend(s[i]-'a');
int p=1;
while(n--){
for(int i=0;i<26;i++)if(a[p][i]){
p=a[p][i];break;
}
}printf("%d\n",l[p]-len+1);
}
}sam;
int T;
int main(){
scanf("%d",&T);
while(T--)sam.solve();
return 0;
}