HDU 2609 How many(最小表示+set)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2609

题目大意：

题目大意有n个有01组成的字符串，每个字符串都代表一个项链，
那么该字符串就是一个环状的结构，求可以经过循环旋转，例如0110 -> 1100 -> 1001 -> 0011->0110，最后不同的串有多少个。

解题思路：求出各个字符串的最小表示，加进set去重就好了。

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<set>
 6 using namespace std;
 7 const int N=1e6+5;
 8 
 9 int len;
10 char p[N];
11 
12 //求最大/最小表示
13 int min_max_express(int flag){
14     int i=0,j=1,k=0;
15     while(i<len&&j<len&&k<len){
16         int t=p[(i+k)%len]-p[(j+k)%len];
17         if(t==0) k++;
18         else{
19             if(flag){
20                 if(t<0) j+=k+1;
21                 else i+=k+1;
22             }
23             else{
24                 if(t>0) j+=k+1;
25                 else i+=k+1;
26             }
27             if(i==j) j++;
28             k=0;
29         }
30     }
31     return min(i,j);
32 }
33 
34 int main(){
35     int n;
36     while(~scanf("%d",&n)){
37         set<string>st;
38         for(int i=0;i<n;i++){
39             scanf("%s",p);
40             len=strlen(p);
41             char tmp[105];
42             int cnt=0,min_idx;
43             min_idx=min_max_express(1);
44             for(int j=0;j<len;j++){
45                 int idx=(min_idx+j)%len;
46                 tmp[cnt++]=p[idx];
47             }
48             tmp[cnt]='';
49             st.insert(tmp);
50         }
51         printf("%d
",st.size());
52     }
53     return 0;
54 }