拿SAM来求字符串的最小表示很煞笔吧、好吧、只是拿来练习SAM用的、
把字符串自复制一遍、然后建SAM、然后从root开始跑,每次都跑最小编号的结点,在上面跑|S|个结点。然后输出当前结点的信息就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct SAMNode{ int ch[26],fa,len; inline void init(){ fa=-1; len=0; memset(ch,0xff,sizeof(ch)); } }T[50010]; char s[10010]; int tot,last; void add(int c){ int end=++tot; T[end].init(); int tmp=last; T[end].len=T[last].len+1; while(tmp!=-1 && T[tmp].ch[c]==-1){ T[tmp].ch[c]=end; tmp=T[tmp].fa; }if(!~tmp) T[end].fa=0; else{ int next=T[tmp].ch[c]; if(T[tmp].len+1==T[next].len) T[end].fa=next; else{ int np=++tot; T[np].init(); T[np]=T[next]; T[np].len=T[tmp].len+1; T[end].fa=T[next].fa=np; while(tmp!=-1 && T[tmp].ch[c]==next){ T[tmp].ch[c]=np; tmp=T[tmp].fa; } } }last=end; }int main(){ int tc; scanf("%d",&tc); while(tc--){ tot=0; last=0; T[0].init(); scanf("%s",s); int n=strlen(s); for(int i=0;i<n;i++) add(s[i]-'a'); for(int i=0;i<n;i++) add(s[i]-'a'); int o=0; for(int i=0;i<n;i++) for(int j=0;j<26;j++) if(~T[o].ch[j]){ o=T[o].ch[j]; break; }printf("%d\n",T[o].len-n+1); }return 0; }