把一個(gè)長(zhǎng)為len的字符串圍成一個(gè)圈，然后以任意一個(gè)字符作為起點(diǎn)，都會(huì)產(chǎn)生一個(gè)新的長(zhǎng)為len的字符串，字符串的最小表示就是所有新字符串中字典序最小的那個(gè)。
下面這個(gè)函數(shù)就是解決這個(gè)問題的，返回值為字典序最小的串的在原串中的起始位置。
1 int MinimumRepresentation(char *s,int l)//串s[0~l-1]的最小表示位置
2 {
3 int i = 0, j = 1, k = 0,t;
4 while (i < l && j < l && k < l)//找不到比它還小的 或者 完全匹配
5 {
6 t = s[(i+k)%l] - s[(j+k)%l];
7 //if (s[(i+k) >= l ? i+k-l : i+k] == s[(j+k) >= l ? j+k-l : j+k])
8 if (t == 0)
9 k++;//相等的話,檢測(cè)長(zhǎng)度加1
10 else
11 {
12 if (t > 0)//大于的話,s[i]為首的肯定不是最小表示,最大表示就改<
13 i += k + 1;
14 else
15 j += k + 1;
16 if (i == j)
17 j++;
18 k = 0;
19 }
20 }
21 return min(i,j);
22 }
基本想法就是兩個(gè)位置的字符比較，如果s[i+k] > s[j+k]那么i到i+k位置都不是最小表示的位置，所以i直接跳k+1步，反之j直接跳k+1步。
本題代碼：
1 import java.io.*;
2 public class Main {
3 static int minpos(String str)
4 {
5 int p1=0,p2=1,len=0;
6 while(p1<str.length()&&p2<str.length()&&len<str.length())
7 {
8 int res=str.charAt((p1+len)%str.length())-str.charAt((p2+len)%str.length());
9 if(res==0)
10 len++;
11 else
12 {
13 if(res>0) p1+=len+1;//如果是最大表示，則p2+=len+1，下面亦反
14 else p2+=len+1;
15 len=0;
16 p2=p2+(p1==p2?1:0);
17 }
18 }
19 return Math.min(p1, p2)+1;
20 }
21 public static void main(String[] args) throws IOException{
22 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
23 int test=Integer.parseInt(in.readLine());
24 while((test--)!=0)
25 System.out.println(minpos(in.readLine()));
26 }
27
28 }
29