題意：
給出一個(gè)字符串，求其所有循環(huán)同構(gòu)串中字典序最大的串以及最小的串。并且計(jì)算這兩個(gè)串在所有循環(huán)同構(gòu)串中出現(xiàn)的次數(shù)
解法：
第一問，用經(jīng)典的求串的最小表示的算法就可以了。
第二問，利用KMP算法前綴數(shù)組的性質(zhì)，即最大后綴等于最長前綴的位置。從最小表示（最大表示）的位置開始計(jì)算next函數(shù)，將start+len-1位置作合法標(biāo)志，計(jì)算nxt數(shù)組的時(shí)候順便計(jì)算標(biāo)記（與AC自動機(jī)方法相同），然后統(tǒng)計(jì)標(biāo)記個(gè)數(shù)即可～
代碼：（GCC）
1 # include <string.h>
2 # include <stdio.h>
3 # include <stdbool.h>
4 char str[2050000];
5 int pre[2050000];
6 bool end[2050000];
7 int maxpos(int len)
8 {
9 int p1=0,p2=1,l=0,i;
10 while(p1<len&&p2<len&&l<len)
11 {
12 int cmp=str[p1+l]-str[p2+l];
13 if(!cmp)
14 l++;
15 else
16 {
17 if(cmp<0) p1+=l+1;
18 else p2+=l+1;
19 l=0;
20 p2+=(p2==p1);
21 }
22 }
23 return p1<p2?p1:p2;
24 }
25 int minpos(int len)
26 {
27 int p1=0,p2=1,l=0,i;
28 while(p1<len&&p2<len&&l<len)
29 {
30 int cmp=str[p1+l]-str[p2+l];
31 if(!cmp)
32 l++;
33 else
34 {
35 if(cmp>0) p1+=l+1;
36 else p2+=l+1;
37 l=0;
38 p2+=(p2==p1);
39 }
40 }
41 return p1<p2?p1:p2;
42 }
43 int gettimes(int start,int len)
44 {
45 int p,res=0;
46 memset(end,0,sizeof(end));
47 end[start+len-1]=1;
48 pre[start]=start-1;
49 for(p=start+1;p<2*len-1;p++)
50 {
51 pre[p]=pre[p-1];
52 while(pre[p]!=start-1&&str[pre[p]+1]!=str[p]) pre[p]=pre[pre[p]];
53 if(str[pre[p]+1]==str[p]) pre[p]++;
54 if(pre[p]!=start-1&&!end[p]) end[p]=end[pre[p]];
55 res+=end[p];
56 }
57 return res;
58 }
59 int main()
60 {
61 while(gets(str))
62 {
63 int len=strlen(str),i;
64 for(i=len;i<2*len-1;i++) str[i]=str[i-len];
65 str[2*len-1]='\0';
66 int p1=minpos(len);
67 int t1=gettimes(p1,len);
68 printf("%d %d ",p1+1,t1);
69 p1=maxpos(len);
70 t1=gettimes(p1,len);
71 printf("%d %d\n",p1+1,t1);
72 }
73 return 0;
74 }
75