POJ 1509 循环同构的最小表示法

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 #define N 10005
 7 char s[N];
 8 
 9 inline int minpos(char *s)
10 {
11     int l = strlen(s);
12     int i=0 , j=1 , k=0;
13     while(i<l&&j<l&&k<l){ //这里k<l是防止出现所有数都一样导致无限循环
14         if(i == j) j++;
15         else if(s[(i+k)%l]>s[(j+k)%l]){
16             i = i+k+1;
17             k=0;
18         }
19         else if(s[(i+k)%l]<s[(j+k)%l]){
20             j = j+k+1;
21             k=0;
22         }
23         else k++;
24     }
25     return min(i , j)+1;
26 }
27 
28 int main()
29 {
30    // freopen("a.in" , "r" , stdin);
31     int T;
32     scanf("%d" , &T);
33     while(T--)
34     {
35         scanf("%s" , s);
36         printf("%d\n" , minpos(s));
37     }
38     return 0;
39 }