题目链接：http://poj.org/problem?id=1509
题目意思就是求循环字符串的最小表示。
我们用字符串S+S建立SAM，然后从root开始走n步，每次尽量选最小的。
由于 SAM 可以接受 SS 所有的子串，而字典序最小的字符串也必定是 SS 的子串，因此按照上面的规则移动就可以找到一个字典序最小的子串。
这里的right等价类的len显然可以直接扩展到串首，于是开始的位置就是T[o].len-n+1。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct State{
int ch[],fa,len;
void init(){
fa=-;
len=;
memset(ch,-,sizeof(ch));
}
}T[];
char s[];
int cnt=,la;
void Extend(int c){
int end=++cnt,tmp=la;
T[end].init();
T[end].len=T[tmp].len+;
while(tmp!=-&&T[tmp].ch[c]==-){
T[tmp].ch[c]=end;
tmp=T[tmp].fa;
}
if(!~tmp) T[end].fa=;
else{
int ne=T[tmp].ch[c];
if(T[tmp].len+==T[ne].len) T[end].fa=ne;
else{
int np=++cnt;
T[np].init();
T[np]=T[ne];
T[np].len=T[tmp].len+;
T[end].fa=T[ne].fa=np;
while(tmp!=-&&T[tmp].ch[c]==ne){
T[tmp].ch[c]=np;
tmp=T[tmp].fa;
}
}
}
la=end;
}
int main(){
int Test;
scanf("%d",&Test);
while(Test--){
cnt=;
la=;
T[].init();
scanf("%s",s);
int n=strlen(s);
for(int i=;i<n;i++) Extend(s[i]-'a');
for(int i=;i<n;i++) Extend(s[i]-'a');
int o=;
for(int i=;i<n;i++)
for(int j=;j<;j++)
if(~T[o].ch[j]){
o=T[o].ch[j];
break;
}
printf("%d\n",T[o].len-n+);
}
return ;
}