题意：求一个字符串的最小表示的开始下标
就当模板题写了
把字符串重复一遍，再建后缀自动机，贪心的选最小字典序在上面走len步
因为走出来的一定是子串，长度又是len，所以一定是原来的字符串旋转得到的，就解决了
1 const 2 maxn=50010; 3 type 4 node=record 5 go:array[0..25]of longint; 6 step,fa:longint; 7 end; 8 9 var 10 sam:array[0..maxn]of node; 11 s,ans:ansistring; 12 len,tot,last,t:longint; 13 14 procedure add(x:longint); 15 var 16 now,new,q:longint; 17 begin 18 inc(tot); 19 now:=tot; 20 fillchar(sam[now].go,sizeof(sam[now].go),0); 21 sam[now].step:=sam[last].step+1; 22 while (last<>0)and(sam[last].go[x]=0) do 23 begin 24 sam[last].go[x]:=now; 25 last:=sam[last].fa; 26 end; 27 if last=0 then sam[now].fa:=1 28 else 29 begin 30 q:=sam[last].go[x]; 31 if sam[q].step=sam[last].step+1 then sam[now].fa:=q 32 else 33 begin 34 inc(tot); 35 new:=tot; 36 sam[new]:=sam[q]; 37 sam[q].fa:=new; 38 sam[now].fa:=new; 39 sam[new].step:=sam[last].step+1; 40 while (last<>0)and(sam[last].go[x]=q) do 41 begin 42 sam[last].go[x]:=new; 43 last:=sam[last].fa; 44 end; 45 end; 46 end; 47 last:=now; 48 end; 49 50 procedure main; 51 var 52 i,j,k:longint; 53 begin 54 readln(s); 55 s:=s+s; 56 len:=length(s); 57 last:=1; 58 tot:=1; 59 sam[1].fa:=0; 60 sam[1].step:=0; 61 fillchar(sam[1].go,sizeof(sam[1].go),0); 62 for i:=1 to len do 63 add(ord(s[i])-ord('a')); 64 i:=1; 65 j:=0; 66 ans:=''; 67 while j<len>>1 do 68 begin 69 inc(j); 70 for k:=0 to 25 do 71 if sam[i].go[k]<>0 then break; 72 ans:=ans+chr(k+ord('a')); 73 i:=sam[i].go[k]; 74 end; 75 writeln(pos(ans,s)); 76 end; 77 78 begin 79 readln(t); 80 while t<>0 do 81 begin 82 main; 83 dec(t); 84 end; 85 end.