题意：

给一个字符串S，每次可以将它的第一个字符移到最后面，求这样能得到的字典序最小的字符串。输出开始下标

---

 

练习SAM第一题！

SS构造SAM，然后从开始尽量走最小走n步就可以啦

什么？开始位置？！Right集合中最左的位置-len

直接t[u].val-n+1，为什么啊没有一个人的题解解释呜呜呜呜呜呜

想了想，这个最小串Right等价类的最长串一定到了开头位置，卡不掉吧，最小串唯一一定成立，如果不唯一好像只可能是自己吧

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=2e4+5;int n;char s[N];struct State{    int ch[26],par,val;    State():par(0),val(0){memset(ch,0,sizeof(ch));}}t[N<<1];int sz,root,last;inline int nw(int _){t[++sz].val=_;return sz;}void iniSAM(){sz=0;root=last=nw(0);}void extend(int c){    int p=last,np=nw(t[p].val+1);    while(p&&t[p].ch[c]==0) t[p].ch[c]=np,p=t[p].par;    if(p==0) t[np].par=root;    else{        int q=t[p].ch[c];        if(t[q].val==t[p].val+1) t[np].par=q;        else{            int nq=nw(t[p].val+1);            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,0,sizeof(t));    for(int i=1;i<=n;i++) extend(s[i]-'a');    for(int i=1;i<=n;i++) extend(s[i]-'a');    int u=root;    for(int i=1;i<=n;i++)        for(int k=0;k<26;k++) if(t[u].ch[k]) {u=t[u].ch[k];break;}    printf("%d\n",t[u].val-n+1);}int main(){    freopen("in","r",stdin);    int T;scanf("%d",&T);    while(T--){        scanf("%s",s+1);        n=strlen(s+1);        solve();    }}