题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3374
题目大意：给出一个字符串，依次左移一个单位形成一堆字符串，求其字典序最小和最大的字符串需要左移多少位，以及一共有几个这样的字符串(例如0101->1010->0101)。
解题思路：首先可以确定两个字符串出现的次数应该相同，即循环节数目，这个比较容易得到。然后就是最大最小字符串如何得到的问题了，直接暴力肯定超时。。。。
所以这里找到了比较好的方法，转载：http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
求字符串最小表示的方法
(1) 利用两个指针p1, p2。初始化时p1指向s[0], p2指向s[1]。
(2) k = 0开始，检验s[p1+k] 与 s[p2+k] 对应的字符是否相等，如果相等则k++，一直下去，直到找到第一个不同，(若k试了一个字符串的长度也没找到不同，则那个位置就是最小表示位置，算法终止并返回)。则该过程中，s[p1+k] 与 s[p2+k]的大小关系，有三种情况：
(A). s[p1+k] > s[p2+k]，则p1滑动到p1+k+1处 --- 即s1[p1->p1+k]不会
是该循环字符串的“最小表示”的前缀。 k置为0
(B). s[p1+k] < s[p2+k]，则p2滑动到p2+k+1处， k置为0
(C). s[p1+k] = s[p2+k]，则 k++； if (k == len) 返回结果。
注:这里滑动方式有个小细节，若滑动后p1 == p2，将正在变化的那个指针再+1。直到p1、p2把整个字符串都检验完毕，返回两者中小于 len 的值。
(3) 如果 k == len， 则返回p1与p2中的最小值
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=1e6+5; 7 8 int len; 9 int nxt[N]; 10 char p[N]; 11 12 void getnext(){ 13 int i,j; 14 i=0,j=nxt[0]=-1; 15 while(i<len){ 16 while(j!=-1&&p[i]!=p[j]) 17 j=nxt[j]; 18 nxt[++i]=++j; 19 } 20 } 21 22 //求出最大/最小表示 23 int min_max_express(int flag){ 24 int i=0,j=1,k=0; 25 while(i<len&&j<len&&k<len){ 26 int t=p[(i+k)%len]-p[(j+k)%len]; 27 if(t==0) k++; 28 else{ 29 if(flag){ 30 if(t<0) j+=k+1; 31 else i+=k+1; 32 } 33 else{ 34 if(t>0) j+=k+1; 35 else i+=k+1; 36 } 37 if(i==j) j++; 38 k=0; 39 } 40 } 41 return min(i,j)+1; //数组下标从0开始，题目是从1开始 42 } 43 44 int main(){ 45 while(~scanf("%s",p)){ 46 len=strlen(p); 47 int min_idx=min_max_express(1); 48 int max_idx=min_max_express(0); 49 getnext(); 50 int mmin=len-nxt[len]; 51 int res=len%mmin?1:len/mmin; 52 printf("%d %d %d %d ",min_idx,res,max_idx,res); 53 } 54 return 0; 55 }