Posted on 2009-08-27 16:50
Uriel 阅读(617)
评论(0) 编辑 收藏 引用 所属分类:
POJ
校个人赛遇到才知道最小表示法。。经典，强大，可惜还没完全懂，只是勉强照搬。
/**//*Problem: 1509 User: Uriel
Memory: 144K Time: 16MS
Language: C Result: Accepted*/
#include<stdio.h>
#include<string.h>
int min(int a, int b)
{
return a <= b ? a : b;
}
int MinimumRepresentation(char *s, int l)
{
int i = 0, j = 1, k = 0, t;
while (i < l && j < l && k < l)
{
t = s[(i + k)%l] - s[(j + k)%l];
if (!t) ++ k;
else
{
if (t > 0) i = i + k + 1;
else j = j + k + 1;
if (i == j) ++j;
k = 0;
}
}
return min(i,j);
}
int x,len,i,t;
char str[10010];
int main()
{
scanf("%d",&t);
getchar();
while(t--)
{
memset(str,0x00,sizeof(str));
scanf("%s",str);
len=strlen(str);
x=MinimumRepresentation(str,len);
printf("%d\n",x+1);
}
return 0;
}