题目链接：
题目描述：
给出一个文本串，找出顺时针或者逆时针循环旋转后，字典序最大的那个字符串，字典序最大的字符串如果有多个，就输出下标最小的那个，如果顺时针和逆时针的起始下标相同，则输出顺时针。
解题思路：
看到题目感觉后缀数组可以搞，正准备犯傻被队友拦下了，听队友解释一番，果断丢锅给队友。赛后试了一下后缀数组果然麻烦的不要不要的(QWQ)，还是最大最小表示法 + KMP来的干净利索。
最大表示法：对于一个长度为len文本串，经过循环旋转得到长度为len的新串，新串是所有循环旋转得到的串中字典序最大的。
实现方法：对于文本串s，我们可以设定两个指针i, j.
刚开始的时候i = 0, j = 1;
当s[i] == s[j]时, (设定指针k) 从i, j 开始比较，直到s[i+k]!= s[j+k]；
如果s[i+k] < s[j+k], i += k + 1, k = 0;
因为s[i+k] < s[j+k],证明以i开头的串已经没有意义，以i开头的串一定小于以j开头的串的字典序，所以把指针i移动到(i+k+1)的位置继续和以j开头的串比较；
依此得, j += k + 1, k = 0, 当前j 为最大表示串的起始点；
最后返回min(i, j)即可。(最小表示法把上面的大于改成小于就ok!)
代码实现：
1 int Max_Repre (char s[], int n) 2 { 3 int i = 0, j = 1, k = 0; 4 while (i<n && j<n && k<n) 5 { 6 int nu = s[(i+k)%n] - s[(j+k)%n]; 7 8 if ( !nu ) k++; 9 else 10 { 11 if (nu < 0) 12 i += k + 1; 13 else 14 j += k + 1; 15 16 if (i == j) 17 j ++; 18 k = 0; 19 20 } 21 } 22 return min (i, j); 23 }
下面是Hdu 5442 代码，还是要比sa好很多的 (惬意！！！！)
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 20010; 8 int Next[maxn]; 9 10 int Max_Repre (char s[], int n) 11 { 12 int i = 0, j = 1, k = 0; 13 while (i<n && j<n && k<n) 14 { 15 int nu = s[(i+k)%n] - s[(j+k)%n]; 16 17 if ( !nu ) k++; 18 else 19 { 20 if (nu < 0) 21 i += k + 1; 22 else 23 j += k + 1; 24 25 if (i == j) 26 j ++; 27 k = 0; 28 29 } 30 } 31 return min (i, j); 32 } 33 34 int Get_Next (char s[], int n) 35 { 36 int k = -1, i = 0; 37 Next[0] = -1; 38 39 while (i < n) 40 { 41 if (k == -1 || s[k]==s[i]) 42 Next[++i] = ++k; 43 44 else 45 k = Next[k]; 46 } 47 48 if (n % (n - Next[n])) 49 return n; 50 return n - Next[n]; 51 } 52 53 void display (char a[], char s[], int x, int n) 54 { 55 for (int i=0; i<n; i++) 56 a[i] = s[(x+i)%n]; 57 58 a[n] = 0; 59 } 60 61 //a大，return true，b大 return false 62 bool Judge (int a, int b, char A[], char B[]) 63 { 64 int k = strcmp (A, B); 65 66 if (k == 0) 67 return a<=b ? true:false; 68 return k>0?true:false; 69 } 70 71 int main () 72 { 73 int t, n, k, a, b; 74 char S[maxn], A[maxn], B[maxn]; 75 scanf ("%d", &t); 76 77 while (t --) 78 { 79 scanf ("%d %s", &n, S); 80 81 k = Get_Next (S, n); 82 a = Max_Repre (S, n); 83 display (A, S, a, n); 84 85 strrev (S); 86 b = Max_Repre (S, n); 87 display (B, S, b, n); 88 b = (n - b - 1) % k; 89 90 if (Judge (a, b, A, B)) 91 printf ("%d 0 ", a + 1); 92 else 93 printf ("%d 1 ", b + 1); 94 } 95 return 0; 96 }