BZOJ 2176 Strange string 最小表示法

题目大意：给定一个串S，求最小表示法

n<=1000W，实在不敢写后缀自己主动机，就去学了最小表示法= =

记得用unsigned char不然WA= = 数据真是逗- –

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 10001000
using namespace std;
int n;
unsigned char s[M];
int Min_Representation()
{
int i,j,k;
for(i=1,j=2,k=0;i<=n&&j<=n&&k<=n;)
{
int t=s[i+k>n?i+k-n:i+k]-s[j+k>n?j+k-n:j+k];
if(!t) k++;
else
{
if(t>0) i+=k+1;
else j+=k+1;
if(i==j) ++j;
k=0;
}
}
return min(i,j);
}
int main()
{
scanf("%d\n",&n);
fread(s+1,1,n,stdin);
int ans=Min_Representation();
if(ans==1)
fwrite(s+1,1,n,stdout);
else
fwrite(s+ans,1,n-ans+1,stdout),fwrite(s+1,1,ans-1,stdout);
cout<<endl;
return 0;
}