工艺（最小表示法）

工艺

题意：给定长度为 $n$n的序列，求字典序最小的长度为 $n$n且与原序列循环同构的序列

思路：利用最小表示法（也有后缀自动机以及后缀数组的解法）

1. 暴力的比较所有的 $n$n个循环同构的串
2. 纯暴力会被卡到 $O\left(n^2\right)$O(n2)，因此需要加点优化，代码如下

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 3e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int a[maxn];

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    int n=read();
    for(int i=0; i<n; ++i) a[i]=read();
    int i=0, j=1, k=0; //i和j为两个正在比较大小的串的开始位置，k为两者第k个位置
    while(i<n&&j<n&&k<n) {
        if(a[(i+k)%n]==a[(j+k)%n]) k++; //若当前位置相同，则比较下一个位置
        else {
            if(a[(i+k)%n]>a[(j+k)%n]) i+=k+1;
            else j+=k+1;//这两行指前跳过了不可能成为最小表示的串，因为i和j的前k-1个位置都相同
            if(i==j) i++; //j++也行,保证i!=j即可
            k=0; //又从第一个位置开始比较
        }
    }
    int start=min(i,j); //由于上面退出循环可以分为两种情况,(i>=n||j>=n)或(k==n)。若k等于n，则i,j随便输出一个，表示原串所有位置都相同；若是另外的情况，肯定输出i和j中较小的那个
    for(int i=0; i<n; ++i) printf("%d%c", a[(start+i)%n], " \n"[i==n-1]);
}

在这里口胡一个后缀自动机的解法，适用于长度t<=n的字典序最小的。。。

1. 建后缀自动机时用map存边
2. 由于map已经按照第一关键字排序了，因此只需贪心的跑长度为t的串即可(用map.begin()表示字典序最小的边)