题意：给出一个字符串，长度是2*10^4。将它首尾相接形成环，并在环上找一个起始点顺时针或逆时针走一圈，求字典序最大的走法，如果有多个答案则找起始点最小的，若起始点也相同则选择顺时针。
分析：后缀数组。
首先，需要补充后缀数组的基本知识的话，看这个链接。
http://www.cnblogs.com/rainydays/archive/2011/05/09/2040993.html
我利用这道题重新整理了后缀数组的模板如下：
const int MAX_LEN = ;
//call init_RMQ(f[], n) first.
//then call query(a, b) to quest the RMQ of [a, b].
int power[];
int st[MAX_LEN * ][];
int ln[MAX_LEN * ]; //returns the index of the first minimum value in [x, y]
void init_RMQ(int f[], int n)
{
int i, j;
for (power[] = , i = ; i < ; i++)
{
power[i] = * power[i - ];
}
for (i = ; i < n; i++)
{
st[i][] = i;
}
ln[] = -;
for (int i = ; i <= n; i++)
{
ln[i] = ln[i >> ] + ;
}
for (j = ; j < ln[n]; j++)
{
for (i = ; i < n; i++)
{
if (i + power[j - ] - >= n)
{
break;
}
//for maximum, change ">" to "<"
//for the last, change "<" or ">" to "<=" or ">="
if (f[st[i][j - ]] > f[st[i + power[j - ]][j - ]])
{
st[i][j] = st[i + power[j - ]][j - ];
}
else
{
st[i][j] = st[i][j - ];
}
}
}
} int query(int f[], int x, int y)
{
if(x > y)
{
swap(x, y);
}
int k = ln[y - x + ];
//for maximum, change ">" to "<"
//for the last, change "<" or ">" to "<=" or ">="
if (f[st[x][k]] > f[st[y - power[k] + ][k]])
return st[y - power[k] + ][k];
return st[x][k];
} //first use the constructed function
//call function lcp(l, r) to get the longest common prefix of sa[l] and sa[r]
//have access to the member of sa, myrank, height and so on
//height is the LCP of sa[i] and sa[i + 1]
class SuffixArray
{
public:
char* s;
int n, sa[MAX_LEN], height[MAX_LEN], myrank[MAX_LEN];
int tmp[MAX_LEN], top[MAX_LEN]; SuffixArray()
{} //the string and the length of the string
SuffixArray(char* st, int len)
{
s = st;
n = len + ;
make_sa();
make_lcp();
} void make_sa()
{
// O(N * log N)
int na = (n < ? : n);
memset(top, , na * sizeof(int));
for (int i = ; i < n ; i++)
top[myrank[i] = s[i] & 0xff]++;
for (int i = ; i < na; i++)
top[i] += top[i - ];
for (int i = ; i < n ; i++)
sa[--top[ myrank[i]]] = i;
int x;
for (int len = ; len < n; len <<= )
{
for (int i = ; i < n; i++)
{
x = sa[i] - len;
if (x < )
x += n;
tmp[top[myrank[x]]++] = x;
}
sa[tmp[top[] = ]] = x = ;
for (int i = ; i < n; i++)
{
if (myrank[tmp[i]] != myrank[tmp[i-]] ||
myrank[tmp[i]+len]!=myrank[tmp[i-]+len])
top[++x] = i;
sa[tmp[i]] = x;
}
memcpy(myrank, sa , n * sizeof(int));
memcpy(sa , tmp, n * sizeof(int));
if (x >= n - )
break;
}
} void make_lcp()
{
// O(4 * N)
int i, j, k;
for (j = myrank[height[i = k = ] = ]; i < n - ; i++, k++)
{
while (k >= && s[i] != s[sa[j - ] + k])
{
height[j - ] = (k--);
j = myrank[sa[j] + ];
}
}
init_RMQ(height, n - );
} int lcp(int l, int r)
{
return height[query(height, l, r - )];
}
};
先将两个原字符串拼成一个长度是2倍的字符串，便于处理越过原串末尾的情况。
运行后缀数组求顺时针解。
反转这个长字符串，再运行后缀数组，求逆时针解。
比较两个解，得出最终解。
下面我们来分析一下，每次运行后缀数组之后是如何求解的。
设原串长度为len。
首先从sa[len*2]开始依次向前找。即从排序最大的开始向前找。之所以排序最大的不一定是我们要的答案是因为：
1.它可能起始点在后面的附加的串上，并没有构成完整的一圈。
2.我们还要找起始点最小的答案呢。（当然，对于反转后的字符串，我们要找起始点最大的）
在第一次遇到一个起始点小于len的时候，表明这个可能就是答案。但是前面可能有起始点更小的，我们还要继续沿着sa向前找，但找的时候一定要保证字典序是最大的，所以每次向前移动一个，都要观察height(i, i+1)是否>len，如果不是，则说明字典序已经不是最大了。
特别注意，height==len的情况也是不可以的，因为两者相等很有可能表明其中一个的起始点已经等于len。当然也可以对每个都判断一下起始点位置。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define d(x) const int MAX_N = (int)(4e4) + ; //call init_RMQ(f[], n) first.
//then call query(a, b) to quest the RMQ of [a, b].
int power[];
int st[MAX_N * ][];
int ln[MAX_N * ]; //returns the index of the first minimum value in [x, y]
void init_RMQ(int f[], int n)
{
int i, j;
for (power[] = , i = ; i < ; i++)
{
power[i] = * power[i - ];
}
for (i = ; i < n; i++)
{
st[i][] = i;
}
ln[] = -;
for (int i = ; i <= n; i++)
{
ln[i] = ln[i >> ] + ;
}
for (j = ; j < ln[n]; j++)
{
for (i = ; i < n; i++)
{
if (i + power[j - ] - >= n)
{
break;
}
//for maximum, change ">" to "<"
//for the last, change "<" or ">" to "<=" or ">="
if (f[st[i][j - ]] > f[st[i + power[j - ]][j - ]])
{
st[i][j] = st[i + power[j - ]][j - ];
}
else
{
st[i][j] = st[i][j - ];
}
}
}
} int query(int f[], int x, int y)
{
if(x > y)
{
swap(x, y);
}
int k = ln[y - x + ];
//for maximum, change ">" to "<"
//for the last, change "<" or ">" to "<=" or ">="
if (f[st[x][k]] > f[st[y - power[k] + ][k]])
return st[y - power[k] + ][k];
return st[x][k];
} //first use the constructed function
//call function lcp(l, r) to get the longest common prefix of sa[l] and sa[r]
//have access to the member of sa, myrank, height and so on
//height is the LCP of sa[i] and sa[i + 1]
class SuffixArray
{
public:
char* s;
int n, sa[MAX_N], height[MAX_N], myrank[MAX_N];
int tmp[MAX_N], top[MAX_N]; SuffixArray()
{} //the string and the length of the string
SuffixArray(char* st, int len)
{
s = st;
n = len + ;
make_sa();
make_lcp();
} void make_sa()
{
// O(N * log N)
int na = (n < ? : n);
memset(top, , na * sizeof(int));
for (int i = ; i < n ; i++)
top[myrank[i] = s[i] & 0xff]++;
for (int i = ; i < na; i++)
top[i] += top[i - ];
for (int i = ; i < n ; i++)
sa[--top[ myrank[i]]] = i;
int x;
for (int len = ; len < n; len <<= )
{
for (int i = ; i < n; i++)
{
x = sa[i] - len;
if (x < )
x += n;
tmp[top[myrank[x]]++] = x;
}
sa[tmp[top[] = ]] = x = ;
for (int i = ; i < n; i++)
{
if (myrank[tmp[i]] != myrank[tmp[i-]] ||
myrank[tmp[i]+len]!=myrank[tmp[i-]+len])
top[++x] = i;
sa[tmp[i]] = x;
}
memcpy(myrank, sa , n * sizeof(int));
memcpy(sa , tmp, n * sizeof(int));
if (x >= n - )
break;
}
} void make_lcp()
{
// O(4 * N)
int i, j, k;
for (j = myrank[height[i = k = ] = ]; i < n - ; i++, k++)
{
while (k >= && s[i] != s[sa[j - ] + k])
{
height[j - ] = (k--);
j = myrank[sa[j] + ];
}
}
init_RMQ(height, n - );
} int lcp(int l, int r)
{
return height[query(height, l, r - )];
}
}; SuffixArray suffix;
int len;
char ans1[MAX_N], ans2[MAX_N];
int pos1, pos2;
char s[MAX_N]; int work1(char* ans)
{
int p = len * ;
while (suffix.sa[p] >= len)
p--;
for (int i = p - ; i >= ; i--)
{
if (suffix.lcp(i, i + ) <= len)
break;
if (suffix.sa[i] < suffix.sa[p])
{
p = i;
}
}
memcpy(ans, s + suffix.sa[p], len);
ans[len] = ;
return suffix.sa[p];
} int work2(char* ans)
{
int p = len * ;
while (suffix.sa[p] >= len)
p--;
for (int i = p - ; i >= ; i--)
{
if (suffix.lcp(i, i + ) <= len)
break;
if (suffix.sa[i] > suffix.sa[p])
{
p = i;
}
}
memcpy(ans, s + suffix.sa[p], len);
ans[len] = ;
return suffix.sa[p];
} int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &len);
scanf("%s", s);
for (int i = ; i < len; i++)
{
s[len + i] = s[i];
}
suffix = SuffixArray(s, len * );
pos1 = work1(ans1);
reverse(s, s + len * );
suffix = SuffixArray(s, len * );
pos2 = work2(ans2);
pos2 = len - - pos2; if (strcmp(ans1, ans2) > )
{
printf("%d 0\n", pos1 + );
continue;
}else if (strcmp(ans1, ans2) < )
{
printf("%d 1\n", pos2 + );
continue;
}else if (pos1 <= pos2)
{
printf("%d 0\n", pos1 + );
continue;
}else
{
printf("%d 1\n", pos2 + );
}
}
return ;
}