【模板】最小表示法

題目描述

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

他們正在玩一種神奇的游戲，叫 Minecraft。

他們現(xiàn)在要做一個由方塊構(gòu)成的長條工藝品。但是方塊現(xiàn)在是亂的，而且由于機器的要求，他們只能做到把這個工藝品最左邊的方塊放到最右邊。

他們想，在僅這一個操作下，最漂亮的工藝品能多漂亮。

兩個工藝品美觀的比較方法是，從頭開始比較，如果第 $i$ 個位置上方塊不一樣那么誰的瑕疵度小，那么誰就更漂亮，如果一樣那么繼續(xù)比較第 $i+1$ 個方塊。如果全都一樣，那么這兩個工藝品就一樣漂亮。

輸入格式

第一行一個整數(shù) $n$，代表方塊的數(shù)目。

第二行 $n$ 個整數(shù)，每個整數(shù)按從左到右的順序輸出方塊瑕疵度的值。

輸出格式

一行 $n$ 個整數(shù)，代表最美觀工藝品從左到右瑕疵度的值。

樣例 #1

樣例輸入 #1

10
10 9 8 7 6 5 4 3 2 1

樣例輸出 #1

1 10 9 8 7 6 5 4 3 2

提示

• 對于 $20\%$ 的數(shù)據(jù)，$n\le 1000$；
• 對于 $40\%$ 的數(shù)據(jù)，$n\le 10^4$；
• 對于 $100\%$ 的數(shù)據(jù)，$n\le 3\times 10^5$。

題意：

雖然題目給定的是個數(shù)組，但我們可以把問題抽象成：給定一個長度為 n 的字符串 s，找出字典序最小的循環(huán)移位（長度也為 n）。以下的分析我們均用 “串” 來代替數(shù)組。

思路：

SAM 高度壓縮了原串各種長度的所有子串。我們發(fā)現(xiàn)：字符串 s + s 包含 s 的所有循環(huán)移位作為子串。所以如果要找字典序的最小循環(huán)移位，不妨將原串復(fù)制一份，形成一個長度為 2n 的串，選擇所有長度為 n 的子串集合中字典序最小的那個。

我們對長度為 2n 的新串構(gòu)建后綴自動機，從DAG的根節(jié)點開始，每次貪心的走字典序最小的節(jié)點，走 n 步，邊走邊輸出即可。

時間復(fù)雜度：$O(n)$

代碼：

#include<bits/stdc++.h>using namespace std;const int N = 6e5 + 10, M = N << 1;
int n, a[N], len[M], fa[M], np = 1, tot = 1;
map<int, int> ch[M];
vector<int> g[M];void extend(int c)
{int p = np; np = ++tot;len[np] = len[p] + 1;while (p && !ch[p][c]) {ch[p][c] = np;p = fa[p];}if (!p) {fa[np] = 1;}else {int q = ch[p][c];if (len[q] == len[p] + 1) {fa[np] = q;}else {int nq = ++tot;len[nq] = len[p] + 1;fa[nq] = fa[q], fa[q] = fa[np] = nq;while (p && ch[p][c] == q) {ch[p][c] = nq;p = fa[p];}ch[nq] = ch[q];}}
}signed main()
{scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);a[i + n] = a[i];}n <<= 1;for (int i = 0; i < n; ++i) {extend(a[i]);}int p = 1;for (int i = 0; i < n / 2; ++i) {auto pp = ch[p].begin();	//由于map自動按第一關(guān)鍵字排序，因此每次貪心地選擇首元素走就行int ele = (*pp).first;int nd = (*pp).second;printf("%d ", ele);p = nd;}puts("");return 0;
}