题意：
给一个字符串S，每次可以将它的第一个字符移到最后面，求这样能得到的字典序最小的字符串。输出开始下标
练习SAM第一题！
SS构造SAM，然后从开始尽量走最小走n步就可以啦
什么？开始位置？！Right集合中最左的位置-len
直接t[u].val-n+1，为什么啊没有一个人的题解解释呜呜呜呜呜呜
想了想，这个最小串Right等价类的最长串一定到了开头位置，卡不掉吧，最小串唯一一定成立，如果不唯一好像只可能是自己吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e4+;
int n;
char s[N];
struct State{
int ch[],par,val;
State():par(),val(){memset(ch,,sizeof(ch));}
}t[N<<];
int sz,root,last;
inline int nw(int _){t[++sz].val=_;return sz;}
void iniSAM(){sz=;root=last=nw();}
void extend(int c){
int p=last,np=nw(t[p].val+);
while(p&&t[p].ch[c]==) t[p].ch[c]=np,p=t[p].par;
if(p==) t[np].par=root;
else{
int q=t[p].ch[c];
if(t[q].val==t[p].val+) t[np].par=q;
else{
int nq=nw(t[p].val+);
memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));
t[nq].par=t[q].par;
t[q].par=t[np].par=nq;
while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].par;
}
}
last=np;
}
void solve(){
iniSAM();
memset(t,,sizeof(t));
for(int i=;i<=n;i++) extend(s[i]-'a');
for(int i=;i<=n;i++) extend(s[i]-'a');
int u=root;
for(int i=;i<=n;i++)
for(int k=;k<;k++) if(t[u].ch[k]) {u=t[u].ch[k];break;}
printf("%d\n",t[u].val-n+);
}
int main(){
freopen("in","r",stdin);
int T;scanf("%d",&T);
while(T--){
scanf("%s",s+);
n=strlen(s+);
solve();
}
}