hdoj2609

字符串的最小表示法+set判重

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<string.h>
#include<set>
using namespace std;
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int minstr(string s)
{
	int i=0,j=1;
	int len=s.length();
	s+=s;
	while(i<=len-1 && j<=len-1)
	{
		int k=0;
		while(k<=len-1 && s[i+k]==s[j+k])
			k++;
		if(k>=len)
			break;
		if(s[i+k]>s[j+k])
			i=max(i+k+1,j+1);
		else
			j=max(j+k+1,i+1);
	}
	return min(i,j);
}
set<string> hash;
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		getchar();
		while(!hash.empty())
			hash.clear();
		int i;
		char str[110];
		for(i=1;i<=n;i++)
		{
			gets(str);
			string s=str;
			char tmp[110];
			int len=s.length();
			int pos=minstr(s);
			for(int j=pos;j<=pos+len-1;j++)
				tmp[j-pos]=s[j%len];
			tmp[len]='\0';
			s=tmp;
			hash.insert(s);
			
		}
		int ans=hash.size();
		printf("%d\n",ans);
	
	}

//system("pause");
return 0;
}