Problem Description
Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me
How many kinds of necklaces total have.(if two necklaces can equal by rotating ,we say the two necklaces are some).
For example 0110 express a necklace, you can rotate it. 0110 -> 1100 -> 1001 -> 0011->0110.
How many kinds of necklaces total have.(if two necklaces can equal by rotating ,we say the two necklaces are some).
For example 0110 express a necklace, you can rotate it. 0110 -> 1100 -> 1001 -> 0011->0110.
Input
The input contains multiple test cases.
Each test case include: first one integers n. (2<=n<=10000)
Next n lines follow. Each line has a equal length character string. (string only include '0','1').
Each test case include: first one integers n. (2<=n<=10000)
Next n lines follow. Each line has a equal length character string. (string only include '0','1').
Output
For each test case output a integer , how many different necklaces.
Sample Input
4
0110
1100
1001
0011
4
1010
0101
1000
0001
Sample Output
1
2
题意：给你n个字符串 每个字符串从任意一个位置组成循环串 都是同一个串 问到底有多少个不一样的字符串
思路：只要最小表示一样就表示是一样的字符串 所以用map判断一下即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long int
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[]={,,,,,,,,,,,,};
int dir[][]={, ,, ,-, ,,-};
int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};
const int inf=0x3f3f3f3f;
const ll mod=1e9+;
int get_min(string s){
int len=s.length();
int i=; int j=; int k=;
while(i<len&&j<len&&k<len){
int t=s[(i+k)%len]-s[(j+k)%len];
if(!t) k++;
else{
if(t>) i+=(k+);
else j+=(k+);
if(i==j) j++;
k=;
}
}
return i>j?j:i;
}
int main(){
ios::sync_with_stdio(false);
int n;
while(cin>>n){
int ans=;
map<string,bool> mm;
for(int i=;i<=n;i++){
string s;
cin>>s;
int pos=get_min(s);
int len=s.length();
string temp=s.substr(pos)+s.substr(,pos);
if(!mm[temp])
mm[temp]=,ans++;
}
cout<<ans<<endl;
}
return ;
}