hdoj4162——最小表示法

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[300000+10],ans[300000+10];
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int minstr(char s[])
{
	int i=0,j=1;
	int len=strlen(s);
	while(i<=len-1 && j<=len-1)
	{
		int k=0;
		while(k<=len-1 && 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+1,j+1);
		else
			j=max(j+k+1,i+1);
	}
	return min(i,j);
}
int main()
{
	int i;
	while(scanf("%s",s)!=EOF)
	{
		getchar();
		char tmp=s[0];
		int len=strlen(s);
		s[len]=tmp;
		s[len+1]='\0';
		for(i=0;i<=len-1;i++)
		{
			if(s[i+1]>=s[i])
				s[i]='0'+s[i+1]-s[i];
			else
				s[i]='0'+s[i+1]+8-s[i];
		}
		s[len]='\0';
		int pos=minstr(s);
		for(i=pos;i<=pos+len-1;i++)
			ans[i-pos]=s[i%len];
		ans[len]='\0';
		printf("%s\n",ans);

	}

system("pause");
return 0;
}