给一个字符串，这个字符串是首位连起来的，要我们输出从哪个位置开始，顺时针走，还是你时针走，字典序最大
如果字典序最大的字符串有多个，开始的下标越小越好，如果开始的下标又相同，那么顺时针的优先。
原字符串为abab，那么只要在后面加上原字符串，变成abababab#，#是一个很小的字符， 然后进行后缀数组，sa[n-1]就是顺指针字典序最大的下标，n为abababab#的长度
逆时针，只要将字符串倒过来，babababa@，@是一个很大的字符， 然后进行后缀数组， 那么只要遍历rank[0,m) ，找到最大的rank所对应的下标就是逆时针字典序最大的下标。
1 #pragma warning(disable:4996) 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <vector> 6 #include <queue> 7 #include <stack> 8 #include <map> 9 #include <set> 10 #include <algorithm> 11 #include <iostream> 12 #include <functional> 13 #include <string> 14 const int INF = 1<<30; 15 const double eps = 1e-5; 16 typedef long long LL; 17 /* 18 19 */ 20 const int N = 40000 + 10; 21 int rank[N], r[N], height[N], c[N], bucket[N], sa[N], tmp[N]; 22 //[0,n)字符串的长度，[0,m)字符集的大小 23 void buildSa(int n, int m) 24 { 25 int *x = rank, *y = tmp, *t, k, p; 26 for (int i = 0; i<m; ++i) c[i] = 0; 27 for (int i = 0; i<n; ++i) c[x[i] = r[i]]++; 28 for (int i = 1; i<m; ++i) c[i] += c[i - 1]; 29 for (int i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i; 30 31 for (k = 1; k <= n; k <<= 1) 32 { 33 p = 0; 34 for (int i = n - k; i<n; ++i) y[p++] = i; 35 for (int i = 0; i<n; ++i) if (sa[i] >= k) y[p++] = sa[i] - k; 36 37 for (int i = 0; i<n; ++i) bucket[i] = x[y[i]];//按排名收集第一关键字的大小, y[i]是下标，所以把y[i]看做是下标就好理解多了 38 for (int i = 0; i<m; ++i) c[i] = 0; 39 for (int i = 0; i<n; ++i) c[bucket[i]]++; 40 for (int i = 1; i<m; ++i) c[i] += c[i - 1]; 41 for (int i = n - 1; i >= 0; --i) sa[--c[bucket[i]]] = y[i]; 42 43 t = x, x = y, y = t; 44 p = 1; x[sa[0]] = 0; 45 for (int i = 1; i<n; ++i) 46 x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++; 47 if (p >= n) break; 48 m = p; 49 } 50 } 51 52 //h[i] = height[rank[i]] h[i] >= h[i-1] - 1; 53 //[0,n] 54 void makeHeight(int n) 55 { 56 int i, j, k = 0; 57 for (i = 0; i <= n; ++i) rank[sa[i]] = i; 58 //第n个字符的排名是0，sa[rank[i]-1]越界，所以不用去算 59 for (i = 0; i<n; height[rank[i++]] = k) 60 for (k ? k-- : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++); 61 } 62 63 char str[N]; 64 std::string ans1,ans2; 65 int idx1,idx2; 66 int main() 67 { 68 int t,n,m; 69 scanf("%d",&t); 70 while(t--) 71 { 72 ans1 = ans2 = ""; 73 scanf("%d",&n); 74 scanf("%s",str); 75 for(int i=0;i<n;++i) 76 r[i] = str[i] - 'a' + 1; 77 m = n; 78 for(int i=0;i<n;++i) 79 r[m++] = str[i] - 'a' + 1; 80 r[m++] = 0; 81 buildSa(m,27); 82 idx1 = sa[m-1]; 83 //printf("%d ",sa[m-1]); 84 m = n; 85 for(int i=idx1; m--;++i) 86 ans1 += r[i] + 'a' - 1; 87 m = 0; 88 for(int i=n-1;i>=0; --i) 89 r[m++] = str[i] -'a'; 90 for(int i=n-1;i>=0; --i) 91 r[m++] = str[i] -'a'; 92 r[m++] = 26; 93 buildSa(m,27); 94 int ma = rank[0]; 95 idx2 = 0; 96 for(int i=1;i<n;++i) 97 { 98 if(rank[i] >= ma) 99 { 100 ma = rank[i]; 101 idx2 = i; 102 } 103 } 104 m = n; 105 for(int i=idx2;m--;++i) 106 ans2 += r[i] + 'a'; 107 idx1 ++; 108 idx2 = n - idx2; 109 if(ans1 > ans2) 110 { 111 printf("%d %d ",idx1,0); 112 } 113 else if(ans1 < ans2) 114 { 115 printf("%d %d ",idx2,1); 116 } 117 else 118 { 119 if(idx1<=idx2) 120 printf("%d %d ",idx1,0); 121 else 122 printf("%d %d ",idx2,1); 123 } 124 } 125 return 0; 126 }