[字符串最小表示法]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;}