【HDOJ】2609 How many

循环同构的最小表示法。
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 #define MAXN 10005
 5 #define MAXL 105
 6 
 7 char map[MAXN][MAXL];
 8 char buf[MAXL];
 9 
10 int Min_exp(char str[], int len) {
11     int i=0, j=1, k=0;
12     char tmp;
13 
14     while (i<len && j<len && k<len) {
15         tmp = str[(i+k)%len] - str[(j+k)%len];
16         if (tmp == 0) {
17             ++k;
18         } else {
19             if (tmp > 0)
20                 i += k+1;
21             else
22                 j += k+1;
23             if (i == j)
24                 ++j;
25             k = 0;
26         }
27     }
28 
29     return i<j ? i:j;
30 }
31 
32 int main() {
33     int n, m, len;
34     int i, j, k;
35 
36     while (scanf("%d", &n) != EOF) {
37         m = 0;
38         while (n--) {
39             scanf("%s", buf);
40             len = strlen(buf);
41             k = Min_exp(buf, len);
42             j = 0;
43             for (i=k; i<len; ++i)
44                 map[m][j++] = buf[i];
45             for (i=0; i<k; ++i)
46                 map[m][j++] = buf[i];
47             map[m][j] = '';
48             ++m;
49         }
50         n = 1;
51         for (i=1; i<m; ++i) {
52             k = 1;
53             for (j=0; j<i; ++j) {
54                 if (strcmp(map[i], map[j]) == 0) {
55                     k = 0;
56                     break;
57                 }
58             }
59             if (k)
60                 ++n;
61         }
62         printf("%d
", n);
63     }
64 
65     return 0;
66 }