[字符串最小表示法]hdoj 4162：Shape Number(解法2)
大致题意：
? ? 见：http://bbezxcy.iteye.com/blog/1439384
?
大致思路：
? ? 最小表示法果然快啊！！从7000多ms优化到900ms，膜拜Orz。
?
#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;const int inf=1<<30;const int nMax =800000;char sss[nMax];int num[nMax];int minexp(int *s,int x) { int i=0,j=1,k=0,t; while(i<x&&j<x&&k<x) { t=s[ (i+k)%x ]-s[ (j+k)%x ]; if(t==0) k++; else { if(t>0) i+=k+1; else j+=k+1; if(i==j) j++; k=0; } } return i<j?i:j;}int main(){ int i,j,len,a,b,n; while(scanf("%s",sss)!=EOF){ len=strlen(sss); for(i=0;i<len-1;i++){ if(sss[i]<=sss[i+1]){ num[i]=sss[i+1]-sss[i]; } else{ num[i]=8-(sss[i]-sss[i+1]); } } if(sss[len-1]<=sss[0]){ num[len-1]=sss[0]-sss[len-1]; } else{ num[len-1]=8-(sss[len-1]-sss[0]); } n=len; int pos1=minexp(num,n); for(i=pos1;i<len;i++){ printf("%d",num[i]); } for(i=0;i<pos1;i++){ printf("%d",num[i]); }printf("\n"); } return 0;}