最小表示法

定义

最小表示法是用于解决字符串最小表示问题的方法。

循环同构

当字符串 $S$ 中可以选定一个位置 $i$ 满足

$$
S[i\cdots n]+S[1\cdots i-1]=T
$$

则称 $S$ 与 $T$ 循环同构

最小表示

字符串 $S$ 的最小表示为与 $S$ 循环同构的所有字符串中字典序最小的字符串

算法核心

考虑对于一对字符串 $A,B$, 它们在原字符串 $S$ 中的起始位置分别为 $i,j$, 且它们的前 $k$ 个字符均相同，即

$$
S[i \cdots i+k-1]=S[j \cdots j+k-1]
$$

不妨先考虑 $S[i+k]>S[j+k]$ 的情况，我们发现起始位置下标 $l$ 满足 $i\le l\le i+k$ 的字符串均不能成为答案。因为对于任意一个字符串 $S_{i+p}$（表示以 $i+p$ 为起始位置的字符串，$p \in [0, k]$）一定存在字符串 $S_{j+p}$ 比它更优。

所以我们比较时可以跳过下标 $l\in [i,i+k]$, 直接比较 $S_{i+k+1}$

这样，我们就完成了对于暴力的优化。

时间复杂度

$O(n)$

过程

1. 初始化指针 $i$ 为 $0$，$j$ 为 $1$；初始化匹配长度 $k$ 为 $0$
2. 比较第 $k$ 位的大小，根据比较结果跳转相应指针。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同
3. 重复上述过程，直到比较结束
4. 答案为 $i,j$ 中较小的一个

实现

int n,a[300005];
int main(){
    n=read();
    for(int i = 0;i< n;i++) a[i]=read();
    int i = 0,j = 1,k = 0;
    while(i<n&&j<n&&k<n){
        if(a[(i+k)%n]==a[(j+k)%n])k++;
        else{
            a[(i+k)%n]>a[(j+k)%n]? i=i+k+1:j=j+k+1;
            if(i==j)i++;
            k=0;
        }
    }
    i = min(i,j);
    for(int cnt=1;cnt<=n;cnt++){
        cout<<a[i]<<" ";
        i=(i+1)%n;
    }
    return 0;
}