给你一个字符串， 然后把他想象成一个环。 从某一个地方断开，然后逆时针或顺时针， 都可以形成一个字符串， 求字典序最大的那种。 输出断开位置以及是顺时针还是逆时针。
如果两个一样， 输出位置靠前的一个， 如果位置也一样， 输出顺时针的那个。
显然是一个最大表示法。 麻烦的是逆时针的情况， 因为要输出位置靠前的一个。 但是逆时针求出来的是字符串反转之后靠前的， 所以应该求一遍kmp， 找出来最靠后的一个位置。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int maxn = 4e4+;
int a[maxn], b[maxn], pos[maxn], nxt[maxn], c[maxn];
int getMax(int a[], int n)
{
int i, j, k;
for(i = , j = ; i<n&&j<n; ) {
for(k = ; k<n&&a[i+k]==a[j+k]; k++)
;
if(k>=n)
break;
if(a[i+k]>a[j+k])
j += k+;
else
i += k+;
if(i == j)
j++;
}
return i;
}
int solve(string s, int a[], int n)
{
for(int i = ; i < n; i++) {
a[i] = s[i]-'a';
}
for(int i = n; i < *n-; i++) {
a[i] = a[i-n];
}
int pos = getMax(a, n);
return pos;
}
void init_kmp(int m) {
int i = , j = -;
nxt[] = -;
while(i<m) {
if(j == - || c[i] == c[j]) {
++i, ++j;
nxt[i] = j;
} else {
j = nxt[j];
}
}
}
int kmp(int n)
{
int cnt = ;
int i = , j = ;
while(i<*n-) {
if(j == - || b[i] == c[j]) {
i++, j++;
} else {
j = nxt[j];
}
if(j == n) {
pos[cnt++] = i;
j = nxt[j];
}
}
return cnt;
}
int main()
{
int t, n;
string s;
cin>>t;
while(t--) {
cin>>n>>s;
int pos1 = solve(s, a, n);
int num = , flag = -;
reverse(s.begin(), s.end());
int pos2 = solve(s, b, n);
int tmp1 = pos1, tmp2 = pos2;
while(num < n) {
if(a[pos1] > b[pos2]) {
flag = ;
break;
} else if(a[pos1] < b[pos2]) {
flag = ;
break;
} else {
pos1++;
pos2++;
num++;
}
}
int cnt = ;
for(int i = tmp2; i < tmp2+n; i++) {
c[cnt++] = b[i];
}
init_kmp(n);
cnt = kmp(n);
tmp2 = pos[cnt-]%n;
if(num == n) {
if(tmp1+ <= n-tmp2) {
flag = ;
} else {
flag = ;
}
}
if(flag) {
printf("%d %d\n", tmp1+, !flag);
} else {
printf("%d %d\n", n-tmp2, !flag);
}
}
return ;
}