工艺

Description

小敏和小燕是一对好朋友。

他们正在玩一种神奇的游戏，叫Minecraft。

他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。

他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。

两个工艺品美观的比较方法是，从头开始比较，如果第 $i$ 个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第 $i+1$ 个方块。如果全都一样，那么这两个工艺品就一样漂亮。

Input

第一行两个整数 $n$ ，代表方块的数目。

第二行 $n$ 个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。

Output

一行 $n$ 个整数，代表最美观工艺品从左到右瑕疵度的值。

Sample Input

10
10 9 8 7 6 5 4 3 2 1

Sample Output

1 10 9 8 7 6 5 4 3 2

Hint

【数据规模与约定】

对于 $20\%$ 的数据， $n\le 10^3$

对于 $40\%$ 的数据， $n\le 10^4$

对于 $100\%$ 的数据， $n\le3\times10^5$

题解

题目大意：求字典序最小的循环同构字符串

最小表示法板子题（

~~断链为环~~ 断环为链

orz Shq 不会 SAM，只会用最小表示法

将串S连接成SS后建立SAM，每次找最小的儿子跑就好了 --Aufun

最小表示法代码：

const int MAXN = 300000 + 100;

int a[MAXN << 1];
int n;

inline int solve() {
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        if (a[i + k] == a[j + k]) k++;
        else {
            if (a[i + k] > a[j + k]) i += k + 1;
            else j += k + 1;
            k = 0;
            if (i == j) j++;
        }
    }
    return std::min(i, j);
}

int main(int argc, char *argv[]) {
    n = SlowRead();
    up (i, 0, n - 1) a[i + n] = a[i] = SlowRead();
    ll s = solve();
    up (i, 0, n - 1) Print(a[i + s]), putchar(' ');
    return 0;
}

Shq 又双叒叕氵了篇 Blog

「BZOJ 2882」工艺 - 最小表示法