Minimum Expression of String 字符串最小表示

　　十分详细的解释：http://hi.baidu.com/kfkkwlhvxcadotr/item/14a46a2b1f889e152a0f1c5f

几道相关例题的代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cassert>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 char buf[100001];
 9 
10 int minExp(char *s) {
11     int i = 0, j = 1, k = 0, t;
12     int len = strlen(s);
13 
14     while (i < len && j < len && k < len) {
15         t = s[(i + k) % len] - s[(j + k) % len];
16         if (!t) {
17             k++;
18         } else {
19             if (t > 0) i = i + k + 1;
20             else {
21                 j = j + k + 1;
22             }
23             if (i == j) j++;
24             k = 0;
25         }
26 //printf("%d %d %d\n", i, j, k);
27     }
28 
29     return min(i, j);
30 }
31 
32 int main() {
33     int T, n;
34 
35     scanf("%d", &T);
36     while (T-- && ~scanf("%d %s", &n, buf)) {
37         printf("%d\n", minExp(buf));
38         memset(buf, 0, sizeof(buf));
39     }
40 
41     return 0;
42 }

zoj 1729

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cassert>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 char buf[10001];
 9 
10 int minExp(char *s) {
11     int i = 0, j = 1, k = 0, t;
12     int len = strlen(s);
13 
14     while (i < len && j < len && k < len) {
15         t = s[(i + k) % len] - s[(j + k) % len];
16         if (!t) {
17             k++;
18         } else {
19             if (t > 0) i = i + k + 1;
20             else {
21                 j = j + k + 1;
22             }
23             if (i == j) j++;
24             k = 0;
25         }
26 //printf("%d %d %d\n", i, j, k);
27     }
28 
29     return min(i, j) + 1;
30 }
31 
32 int main() {
33     int T;
34 
35     scanf("%d", &T);
36     while (T-- && ~scanf("%s", buf)) {
37         printf("%d\n", minExp(buf));
38         memset(buf, 0, sizeof(buf));
39     }
40 
41     return 0;
42 }

zoj 2006

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cassert>
 4 #include <algorithm>
 5 #include <set>
 6 #include <string>
 7 
 8 using namespace std;
 9 
10 set<string> cnt;
11 char buf[101];
12 
13 int minExp(char *s) {
14     int i = 0, j = 1, k = 0, t;
15     int len = strlen(s);
16 
17     while (i < len && j < len && k < len) {
18         t = s[(i + k) % len] - s[(j + k) % len];
19         if (!t) {
20             k++;
21         } else {
22             if (t > 0) i = i + k + 1;
23             else {
24                 j = j + k + 1;
25             }
26             if (i == j) j++;
27             k = 0;
28         }
29 //printf("%d %d %d\n", i, j, k);
30     }
31 
32     return min(i, j);
33 }
34 
35 void con(char *a){
36     int pos = minExp(a);
37     int len = strlen(a);
38     char tmp[101];
39     
40     strcpy(tmp, a);
41     for (int i = 0; i < len; i++){
42         a[i] = tmp[(pos + i) % len];
43     }
44 }
45 
46 int deal(int n){
47     cnt.clear();
48     for (int i = 0; i < n; i++){
49         scanf("%s", buf);
50         con(buf);
51         cnt.insert(buf);
52     }
53 
54     return cnt.size();
55 }
56 
57 int main(){
58     int n;
59 
60     while (~scanf("%d", &n)){
61         printf("%d\n", deal(n));
62     }
63 
64     return 0;
65 }

hdu 2609

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cassert>
 4 #include <algorithm>
 5 #include <set>
 6 #include <string>
 7 
 8 using namespace std;
 9 
10 set<string> cnt;
11 char buf[300001], tmp[300001];
12 
13 int minExp(char *s) {
14     int i = 0, j = 1, k = 0, t;
15     int len = strlen(s);
16 
17     while (i < len && j < len && k < len) {
18         t = s[(i + k) % len] - s[(j + k) % len];
19         if (!t) {
20             k++;
21         } else {
22             if (t > 0) i = i + k + 1;
23             else {
24                 j = j + k + 1;
25             }
26             if (i == j) j++;
27             k = 0;
28         }
29 //printf("%d %d %d\n", i, j, k);
30     }
31 
32     return min(i, j);
33 }
34 
35 void work() {
36     int len = strlen(buf);
37 
38     tmp[0] = (buf[0] - buf[len - 1] + 8) % 8 + '0';
39     for (int i = 1; i < len; i++){
40         tmp[i] = (buf[i] - buf[i - 1] + 8) % 8 + '0';
41     }
42 
43     int pos = minExp(tmp);
44 
45     for (int i = 0; i < len; i++) {
46         buf[i] = tmp[(pos + i) % len];
47     }
48 }
49 
50 int main() {
51     while (~scanf("%s", buf)) {
52         work();
53         printf("%s\n", buf);
54     }
55 
56     return 0;
57 }

hdu 4162

——written by Lyon