题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2609
题目大意:
给你N(N<10000)条项链,项链长度不超过100,告诉我

总共有多少种项链(如果两个项链通过旋转可以相等,我们说这两个项链是一种)。

思路:用最小表示法唯一表示一个项链。然后set去重就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

char s[10005], t[10005];
set<string> st;

void express(char s[], int n){
    int i=0, j=1, k=0;
    while(i<n&&j<n&&k<n){
        int t=s[(i+k)%n]-s[(j+k)%n];
        if(!t){
            k++;
        }
        else if(t>0){
            i=i+k+1, k=0;
        }
        else{
            j=j+k+1, k=0;
        }
        if(i==j){
            j++;
        }
    }
    strcpy(t, s);
    int p=min(i, j), tot=0;
    for(int i=p; i<n; i++){
        s[tot++]=t[i];
    }
    for(int i=0; i<p; i++){
        s[tot++]=t[i];
    }
    s[tot]=0;
    //printf("::%s\n", s);
    st.insert(s);
    //printf("%d\n", st.size());

}

int main()
{
    int n;
    while(~scanf("%d",&n)){

        st.clear();
        for(int i=0; i<n; i++){
            scanf("%s", s);
            express(s, strlen(s));
        }
        printf("%d\n", st.size());
    }

    return 0;
}