http://acm.hdu.edu.cn/showproblem.php?pid=5442
问题概述：n个字符围成一个环，请从这个环中找出字典序最大的长度为n的字符串，输出它的起始点和方向（0顺1
逆）如果有多个，输出起始点下标小的那个，如果下标相同，输出顺时针的
输入样例： 对应输出：
2 10 1
10 2 0
aaaaaaaakz
10
azazazazaz
环形字符串最大字典序：http://blog.csdn.net/zy691357966/article/details/39854359
求解问题：n个字符串围成一个环，请从这个环中找出字典序最大（或最小）的长度为n的字符串（下标尽可能小）
步骤：
①初始化i=1,j=2,len为字符环长度
②从k=0开始，检验str[i+k]与str[j+k]对应的字符是否相等，如果相等则k++，一直下去，如果k<len时找到了第一个不同，执行步骤③，如果k==len，执行步骤④
③若s[i+k]>s[j+k]，则i滑动到i+k+1处，否则j滑动到j+k+1处，若移动完后i==j，则j++，继续执行步骤②，如果i或j有一个超过len，执行步骤④
④返回i和j小的那个，就是答案
技巧：将字符串完全复制一遍接在原字符串的后面，就可以模拟出一个环
此题题解：顺时针套模板，逆时针将字符串逆序再套一次模板，但是逆时针求出来的下标不是最小的反而是最大
的，需要跑一波KMP
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int net[52222]; int Getmax(int len, char str[]); int main(void) { int T, i, len, ans1, ans2, p, q, flag, temp; char st1[52222], st2[52222]; scanf("%d", &T); while(T--) { scanf("%d", &len); for(i=1;i<=len;i++) { scanf(" %c", &st1[i]); st2[len-i+1] = st2[2*len-i+1] = st1[i]; st1[i+len] = st1[i]; } st1[len*2+1] = st2[len*2+1] = '\0'; ans1 = Getmax(len, st1); /*顺时针套模板，计算出起始下标*/ temp = ans2 = Getmax(len, st2); /*逆时针将字符串逆序再套一次模板，计算出起始下标（是最大的那个）*/ /* --KMP-- */ p = ans2-1, q = ans2; /*将ans2设为起点*/ memset(net, -1, sizeof(net)); net[q] = p; flag = 0; /*标记逆时针字典序最大时下标是否唯一，flag==1表示不唯一*/ while(q<=len*2) { if(p==ans2-1 || st2[p]==st2[q]) { p++, q++; net[q] = p; if(net[p]==ans2+len) net[q] = ans2+len, flag = 1; /*找到相同字符串，但下标更小！*/ } else p = net[p]; } if(flag==1) { for(q=2*len;q>=ans2+len;q--) { if(net[q]==ans2+len) { ans2 = 2*len-q+1; break; } } } else ans2 = len-ans2+1; st1[ans1+len] = st2[temp+len] = '\0'; //puts(st1+ans1), puts(st2+temp); if(strcmp(st1+ans1, st2+temp)>0) printf("%d 0\n", ans1); else if(strcmp(st1+ans1, st2+temp)<0) printf("%d 1\n", ans2); else { if(ans1<=ans2) printf("%d 0\n", ans1); else printf("%d 1\n", ans2); } } return 0; } int Getmax(int len, char str[]) { int i, j, k, temp; i = 1, j = 2, k = 0; while(i<=len && j<=len && k<=len) { temp = str[i+k]-str[j+k]; if(temp==0) k++; else { if(temp>0) j = max(j+k+1, i+1); /*可以直接j = j+k+1，下同*/ else i = max(i+k+1, j+1); if(i==j) j++; k = 0; } } if(i<=j) return i; return j; }
