最小表示法

原理

见《进阶指南》第75页。

模板题

洛谷-P1368-【模板】最小表示法

#include <iostream>
using namespace std;

const int N = 300010;
int n, str[2 * N];

int solve () {
    for (int i = 1; i <= n; ++ i) str[n + i] = str[i];
    int i = 1, j = 2, k;
    while (i <= n && j <= n) {
        k = 0;
        while (k < n && str[i + k] == str[j + k]) ++ k;
        if (k == n) break;
        if (str[i + k] > str[j + k]) {
            i = i + k + 1;
            if (i == j) ++ i;
        } else {
            j = j + k + 1;
            if (i == j) ++ j;
        }
    }
    return min(i, j);
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &str[i]);

    int pos = solve();
    for (int i = pos; i <= n; ++ i) printf("%d ", str[i]);
    for (int i = 1; i <= pos - 1; ++ i) printf("%d ", str[i]);
    return 0;
}