Posted on 2009-11-02 18:13
小強摩羯座 閱讀(413)
評論(0) 編輯 收藏 所屬分類:
算法編程
/**//*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;
}
//串的同構是，在若干次循環位移后可以變成相同
static boolean isIsomorphism(String s1, String s2)
{
char[] u = (s1+s1).toCharArray();
char[] w = (s2+s2).toCharArray();
int i = 0;
int j = 0;
int len = s1.length();
while(i < u.length && j < w.length)
{
int k = 0;
while((i+k) < u.length && (j+k)<u.length && u[i+k] == w[j+k])k++;//&& k < len
System.out.println(k);
if(k >= len) return true;
if(u[i+k] > w[j+k])i = i+k+1;
else j = j+k+1;
}
return false;
}