给定一个字符环，对每个在环上顺时针走一圈可以得到的字符串排序。

题解

把环断开然后复制一遍，这样能走到的 n n 个字符串相当于从前 n n 个字符向后走 n n 步所得到的字符串，现在要对这些东西排序嘛，就直接用后缀数组对后缀排序就好啦，因为那些起点在后 n n 个字符的后缀对答案没有影响，他们在哪里都无所谓，而所有合法的串后面添上一段字符也不会影响他们的相对位置。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAX_N = 1e5 * 2;
int n;
int sa[MAX_N + 1], rank[MAX_N + 1];
char s[MAX_N + 1];
inline void suffixArray() {
    static int set[MAX_N + 1], a[MAX_N + 1];
    std::copy(s + 1, s + n + 1, set + 1);
    std::sort(set + 1, set + n + 1);
    int *end = std::unique(set + 1, set + n + 1);
    for (int i = 1; i <= n; i++) a[i] = std::lower_bound(set + 1, end, s[i]) - set;
    static int fir[MAX_N + 1], sec[MAX_N + 1], tmp[MAX_N + 1], buc[MAX_N + 1];
    std::fill(buc, buc + n + 1, 0);
    for (int i = 1; i <= n; i++) buc[a[i]]++;
    for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
    for (int i = 1; i <= n; i++) rank[i] = buc[a[i] - 1] + 1;
    for (int t = 1; t <= n; t *= 2) {
        for (int i = 1; i <= n; i++) fir[i] = rank[i];
        for (int i = 1; i <= n; i++) sec[i] = i + t > n ? 0 : rank[i + t];
        std::fill(buc, buc + n + 1, 0);
        for (int i = 1; i <= n; i++) buc[sec[i]]++;
        for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
        for (int i = 1; i <= n; i++) tmp[n - --buc[sec[i]]] = i;
        std::fill(buc, buc + n + 1, 0);
        for (int i = 1; i <= n; i++) buc[fir[i]]++;
        for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
        for (int j = 1, i; j <= n; j++) i = tmp[j], sa[buc[fir[i]]--] = i;
        bool unique = true;
        for (int j = 1, i, last = 0; j <= n; j++) {
            i = sa[j];
            if (!last) rank[i] = 1;
            else if (fir[i] == fir[last] && sec[i] == sec[last]) rank[i] = rank[last], unique = false;
            else rank[i] = rank[last] + 1;
            last = i;
        }
        if (unique) break;
    }
}
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) s[n + i] = s[i];
    n *= 2;
    suffixArray();
    for (int i = 1; i <= n; i++) {
        if (sa[i] <= n / 2) putchar(s[sa[i] + n / 2 - 1]);
    }
    putchar('\n');
    return 0;
}