最小表示法

定义

求 \(\text{argmin}_{i=1}^n (S_i\sim S_n+S_1\sim S_{i-1})\)。通俗地说，不断将字符串末尾的字符移到开头，得到的 \(n\) 个字符串中的字典序最小者即为字符串的 最小表示。

暴力求法

在得知 \(i\in[1,k)\) 时使得 \(S_i\sim S_n+S_1\sim S_{i-1}\) 最小的 \(i\) 时，可以直接将其和 \(S_k\sim S_n+S_1\sim S_{k-1}\) 比较，得出 \(i\in[1,k]\) 时使得 \(S_i\sim S_n+S_1\sim S_{i-1}\) 最小的 \(i\)。虽然随机数据下表现良好，但是可以构造形如 \(aa\cdots ab\) 的数据将其卡成 \(O(n^2)\)。

后缀数组

求出 \(S_1\sim S_n+S_1\sim S_n\) 的后缀数组，然后 \(1\sim n\) 中 \(rk\) 最小者即为最小表示。证明显然。

\(O(n)\) 做法

原理

令 \(f(i)=S_i\sim S_n+S_1\sim S_{i-1}\)，若 \(f(i)>f(j)\) 且 \(f(i)_1\sim f(i)_k=f(j)_1\sim f(j)_k\)（令 \(g(i,j)=\max_{k=1}^n[f(i)_1\sim f(i)_k=f(j)_1\sim f(j)_k]\cdot k\)），则 \(\forall p\in[1,k],f(i+k)>f(j+k)\)。也就是 \(\forall p\in[i,i+k]\)，\(p\) 均不会成为最小表示。

做法

仍然是维护当前的最小表示 \(i\) 和对应的集合 \([1,j]\)。比较 \(f(i)\) 和 \(f(j+1)\)，如果 \(f(i)<f(j+1)\)，则将 \(j\) 赋为 \(j+g(i,j+1)+1\)，否则将 \(i\) 赋为 \(j+1\)，将 \(j\) 赋为 \(\max(j+1,i+g(i,j+1)+1)\)。

时间复杂度

模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=300010;
#define Md(p) ((p)>=n?(p)-n:(p))
int n,i,j,k,p;
int a[maxn]; 
int main(){
	scanf("%d",&n);
	for(i=0;i<n;++i) scanf("%d",a+i);
	i=0;
	for(j=1;j<n;++j){
		k=0;
		while(k<=n&&a[Md(i+k)]==a[Md(j+k)]) ++k;
		if(a[Md(i+k)]>a[Md(j+k)]){
			p=j;
			j=max(j,i+k);
			i=p;
		}
		else j=j+k;
	}
	for(j=0;j<n;++j) printf("%d ",a[Md(i+j)]);
	return 0;
}