其实是很裸的一道题，可能是因为几乎没用过扩展KMP，只想到用后缀数组，但这题的常数卡的很厉害，不用扩展KMP应该是过不了的。
扩展KMP能求出一个串所有后缀串(即s[i...len])和模式串的最长公共前缀。于是只要将这个串复制一遍，求出该串每个后缀与其本身的最长公共前缀即可，当公共前缀>=len时，显然相等，否则只要比较下一位就能确定这个串与原串的大小关系。
至于重复串的问题，只有当这个串有循环节的时候才会产生重复串，用KMP的next数组求出最小循环节，用长度除以最小循环节得到循环节个数，在将3个答案都除以循环节个数即可。
1 #include <string.h> 2 #include <stdio.h> 3 #define MAXN 2000005 4 int cas; 5 char s[MAXN],s2[MAXN]; 6 int next[MAXN],ext[MAXN]; 7 int max(int x,int y){return x>y?x:y;} 8 int len; 9 int ExKMP(char *t,char *s){ 10 int lent=len,lens=len*2,ans=0; 11 next[1]=lent; 12 int j=1,k=2; 13 while(j<lent&&t[j]==t[j+1])++j; 14 next[2]=j-1; 15 for(int i=3;i<=lent;i++){ 16 if(next[i-k+1]<k+next[k]-i)next[i]=next[i-k+1]; 17 else{ 18 j=max(k+next[k]-i,0); 19 while(i+j<=lent&&t[i+j]==t[j+1])++j; 20 next[i]=j,k=i; 21 } 22 } 23 j=1,k=1; 24 while(j<=lent&&j<=lens&&s[j]==t[j])++j; 25 ext[1]=j-1; 26 if(ext[1]==lent)ans++; 27 for(int i=2;i<=lens;i++){ 28 if(next[i-k+1]<k+ext[k]-i)ext[i]=next[i-k+1]; 29 else{ 30 j=max(k+ext[k]-i,0); 31 while(i+j<=lens&&j<lent&&s[i+j]==t[j+1])++j; 32 ext[i]=j,k=i; 33 } 34 if(ext[i]==lent)ans++; 35 } 36 return ans; 37 } 38 int main(){ 39 //freopen("test.in","r",stdin); 40 scanf("%d",&cas); 41 for(int ca=1;ca<=cas;ca++){ 42 scanf("%s",s+1); 43 len=strlen(s+1); 44 for(int i=1;i<=len;i++)s2[i]=s2[i+len]=s[i]; 45 s2[len*2+1]='\0'; 46 ExKMP(s,s2); 47 int x1=0,x3=0; 48 for(int i=1;i<=len;i++){ 49 if(ext[i]<len){ 50 if(s2[i+ext[i]]<s[ext[i]+1])x1++; 51 else x3++; 52 } 53 } 54 next[1]=0; 55 for(int i=2,j=0;i<=len;i++){ 56 while(j>0&&s[i]!=s[j+1])j=next[j]; 57 if(s[i]==s[j+1])++j; 58 next[i]=j; 59 } 60 int tot=1; 61 if(len%(len-next[len])==0)tot=len/(len-next[len]); 62 printf("Case %d: %d %d %d\n",ca,x1/tot,1,x3/tot); 63 } 64 return 0; 65 }