hdu2609最小表示法

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=;
struct elem
{
char str[];
int len;
bool operator <(const elem &rhs)const{
return len<rhs.len||(len==rhs.len&&strcmp(str,rhs.str)<=);
}
bool operator == (const elem &rhs)const{
return len==rhs.len&&strcmp(str,rhs.str)==;
}
}P[maxn];
char s[];
int MinRepresstation(char * S, int len ) {
int i = , j = , k = ;
while(i < len && j < len)
{
k = ;
while(k < len && S[(i + k)%len] == S[(j + k)%len])
k++;
if(k >= len)
break;
if(S[(i + k)%len] > S[(j + k)%len])
i = max(i + k + , j + );
else
j = max(i + , j + k + );
}
return min(i ,j);
}
int main()
{
int n;
while(scanf("%d",&n)==)
{
for(int i=; i<n; i++)
{
scanf("%s",s);
P[i].len=strlen(s);
int d=MinRepresstation(s,P[i].len);
for(int j=;j<P[i].len; j++)
P[i].str[j]=s[ (d+j)%P[i].len ];
P[i].str[P[i].len]=;
}
sort(P,P+n);
int num=unique(P,P+n)-P;
printf("%d\n",num); } return ;
}
上一篇:搭建 Android 开发环境,初试HelloWorld (win7) (上) (转)


下一篇:LLinux系统编程(10)——进程间通信之管道