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