題目大意：
給定一個字符串S， 可以通過向左移位得到另一個字符串。例如，S="SKYLONG", 通過位移得到的所有字符串（後面的數字表示rank，即第幾個）：
SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7
求出一個字符串經位移後的所有字符串中字典序最小和字典需最大的rank，以及他們出現的次數。
分析與總結：
經過分析，很快可以得到大概的思路：
1. 把S復制成2倍
2. 找出字典序最小和最大的字符串
3. 直接KMP求出他們的次數即可。
關鍵在於第二步。 第一次做時直接枚舉，結果TLE了。勢必要用一個效率更高的方法找到字典序最小和最大的字符串。
經過百度得知這個方法就是“最小最大表示法”。
資料：
【淺析“最小表示法”思想在字符串循環同構問題中的應用--03 周源】：1.論文 2.ppt
代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000005;
char S[MAXN*2];
char first[MAXN];
char last[MAXN];
int rank_first, rank_last;
int next[MAXN];
void getNext(char* S,int* next){
int n=strlen(S);
next[0]=next[1]=0;
for(int i=1; i<n; ++i){
int j=next[i];
if(j && S[i]!=S[j]) j=next[j];
next[i+1] = S[i]==S[j]?1+j:0;
}
}
int find(char* S,char* P,int* next){
getNext(P,next);
int n=strlen(S);
int m=strlen(P);
int j=0;
int cnt=0;
for(int i=0; i<n; ++i){
while(j && S[i]!=P[j]) j=next[j];
if(S[i] == P[j]) ++j;
if(j==m){
++cnt;
}
}
return cnt;
}
//最小表示法
void getMin(char* S){
int i=0, j=1;
int len=strlen(S);
len >>= 1;
while(i<len && j<len){
int k=0;
while(k<len && S[i+k]==S[j+k])
++k;
if(k >= len)
break;
if(S[i+k] > S[j+k])
i = max(i+k+1,j+1);
else
j = max(i+1,j+k+1);
}
int pos=min(i,j);
rank_first=pos+1;
for(int i=0; i<len; ++i)
first[i] = S[pos++];
first[len] = '\0';
}
//最大表示法
void getMax(char* S){
int i=0, j=1;
int len=strlen(S);
len >>= 1;
while(i<len && j<len){
int k=0;
while(k<len && S[i+k]==S[j+k])
++k;
if(k >= len)
break;
if(S[i+k] < S[j+k])
i = max(i+k+1,j+1);
else
j = max(i+1,j+k+1);
}
int pos=min(i,j);
rank_last=pos+1;
for(int i=0; i<len; ++i)
last[i] = S[pos++];
last[len] = '\0';
}
int main(){
while(scanf("%s",S)!=EOF){
int len=strlen(S);
for(int i=0; i<len; ++i){
S[len+i] = S[i];
}
S[2*len] = '\0';
// 先找到字典需最小的和最大的排位
getMin(S);
getMax(S);
printf("%d %d %d %d\n",rank_first,find(S+1,first,next),rank_last,find(S+1,last,next));
}
return 0;
}
