P1368 【模板】最小表示法 （后缀自动机）

【模板】最小表示法 - 洛谷

正解是线性的，但是这题s的范围好像不是很大，后缀自动机也能水过去qaq。

虽然学的时候很痛苦，但是用起来真爽啊hhhh

咳咳，回到正题。这道题求字典序最小，又是最后一个移到第一个的典中典，无疑就是把数组复制一份接上，造sam找字典序最小啦。此时上后缀自动机可以快速解决。每次都找当前字典序最小的字符遍历即可。

map一维表示这点上的数字，二维是下一个点的下标。

/*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define db(x) cerr<<(#x)<<" "<<(x)<<" "<<endl;
#define endl "\n"
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=3e5+10;
int n,las=1,cnt=1;
struct node{
    map<int,int>ch;
    int len,fa;
}tre[maxn<<1];
void ex_sam(int c){
    int p=las,np=las=++cnt;
    tre[np].len=tre[p].len+1;
    for(;p&&!tre[p].ch[c];p=tre[p].fa)tre[p].ch[c]=np;
    if(p==0)tre[np].fa=1;//到根节点 
    else{
        int q=tre[p].ch[c];
        if(tre[q].len==tre[p].len+1)tre[np].fa=q;//刚好接上 
        else{
            int nq=++cnt;
            tre[nq]=tre[q];tre[nq].len=tre[p].len+1;
            tre[q].fa=tre[np].fa=nq;
            for(;p&&tre[p].ch[c]==q;p=tre[p].fa)tre[p].ch[c]=nq;
        }//分点，复制一份接上 
    }
}
int s[maxn];
signed main(){
	fast cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=2;i++){
		for(int j=1;j<=n;j++) ex_sam(s[j]);
	}
	int now=1;
	for(int i=1;i<=n;i++){
		map<int,int>::iterator x=tre[now].ch.begin();
		now=(*x).second;
		cout<<(*x).first<<' ';
	}
}