hdu 2609 How many (字符串的最小表示法+set)

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月13日 星期六 02时44分21秒
 4File Name :code/hdu/2609.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E4+7;
34int n;
35char s[N][105];
36set<string>se;
37int minRep(char *s)
38{
39    int n = strlen(s);
40    int i = 0 ;
41    int j = 1 ;
42    int k = 0 ;
43    while (i<n&&j<n&&k<n)
44    {
45	int t  = s[(i+k)%n] - s[(j+k)%n];
46	if (t==0) k++;
47	else 
48	{
49	    if (t>0)
50		i+=k+1;
51	    else j+=k+1;
52	    if (i==j) j++;
53	    k = 0 ;
54	}
55    }
56    return i<j?i:j;
57}
58int main()
59{
60	#ifndef  ONLINE_JUDGE 
61	freopen("code/in.txt","r",stdin);
62  #endif
63	while (~scanf("%d",&n))
64	{
65	    ms(s,0);
66	    se.clear();
67	  //  cout<<"n:"<<n<<endl;
68	    char tmp[105];
69	    for ( int i = 0 ; i < n;  i++)
70	    {
71		scanf("%s",tmp);
72//		cout<<"tmp:"<<tmp<<endl;
73		int k = minRep(tmp);
74//		cout<<"k:"<<k<<endl;
75		int cnt = 1;
76		int len = strlen(tmp);
77		for ( int j = k ; cnt <= len ; j++,cnt++)
78		    s[i][cnt-1] = tmp[j%len];
79		se.insert(string(s[i]));
80	    }
81//	for ( int i = 0 ; i < n;  i++) cout<<"s[i]:"<<s[i]<<endl;
82//
83	    int ans = se.size();
84	    printf("%d\n",ans);
85	}
86  #ifndef ONLINE_JUDGE  
87  fclose(stdin);
88  #endif
89    return 0;
90}