Posted on 2009-08-27 16:50
Uriel 阅读(621)
评论(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;
}

