题目链接：
题目描述：
给出一个文本串，找出顺时针或者逆时针循环旋转后，字典序最大的那个字符串，字典序最大的字符串如果有多个，就输出下标最小的那个，如果顺时针和逆时针的起始下标相同，则输出顺时针。
解题思路：
看到题目感觉后缀数组可以搞，正准备犯傻被队友拦下了，听队友解释一番，果断丢锅给队友。赛后试了一下后缀数组果然麻烦的不要不要的(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!)
代码实现：
int Max_Repre (char s[], int n)
{
int i = , j = , k = ;
while (i<n && j<n && k<n)
{
int nu = s[(i+k)%n] - s[(j+k)%n]; if ( !nu ) k++;
else
{
if (nu < )
i += k + ;
else
j += k + ; if (i == j)
j ++;
k = ; }
}
return min (i, j);
}
下面是Hdu 5442 代码，还是要比sa好很多的 (惬意！！！！)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = ;
int Next[maxn]; int Max_Repre (char s[], int n)
{
int i = , j = , k = ;
while (i<n && j<n && k<n)
{
int nu = s[(i+k)%n] - s[(j+k)%n]; if ( !nu ) k++;
else
{
if (nu < )
i += k + ;
else
j += k + ; if (i == j)
j ++;
k = ; }
}
return min (i, j);
} int Get_Next (char s[], int n)
{
int k = -, i = ;
Next[] = -; while (i < n)
{
if (k == - || s[k]==s[i])
Next[++i] = ++k; else
k = Next[k];
} if (n % (n - Next[n]))
return n;
return n - Next[n];
} void display (char a[], char s[], int x, int n)
{
for (int i=; i<n; i++)
a[i] = s[(x+i)%n]; a[n] = ;
} //a大，return true，b大 return false
bool Judge (int a, int b, char A[], char B[])
{
int k = strcmp (A, B); if (k == )
return a<=b ? true:false;
return k>?true:false;
} int main ()
{
int t, n, k, a, b;
char S[maxn], A[maxn], B[maxn];
scanf ("%d", &t); while (t --)
{
scanf ("%d %s", &n, S); k = Get_Next (S, n);
a = Max_Repre (S, n);
display (A, S, a, n); strrev (S);
b = Max_Repre (S, n);
display (B, S, b, n);
b = (n - b - ) % k; if (Judge (a, b, A, B))
printf ("%d 0\n", a + );
else
printf ("%d 1\n", b + );
}
return ;
}