BZOJ2882:工艺 STL+后缀自动机

思路:这大概也算是后缀自动机裸题了吧.

虽然最小表示法最靠谱,不过我还是懒,于是用map水了一发.好方便啊~`

注意数据范围有一些不靠谱,详情见代码= =

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
#define N 500010
map<int,int>tranc[N<<1];int pa[N<<1],len[N<<1],cnt,root,last;
inline int newnode(int l){
    len[++cnt]=l;return cnt;
}
inline void init(){
    root=last=newnode(0);
}
 
int a[N<<1];
int main(){
    int n;scanf("%d",&n);register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]),a[i+n]=a[i];
    int p,np,q,nq,y;
    for(init(),i=1;i<=n*2;++i){
        np=newnode(len[last]+1);
        for(p=last,y=a[i];tranc[p].find(y)==tranc[p].end();p=pa[p])tranc[p][y]=np;
        if(!p)pa[np]=root;
        else{
            q=tranc[p][y];
            if(len[q]==len[p]+1)pa[np]=q;
            else{
                nq=newnode(len[p]+1),pa[nq]=pa[q],pa[q]=pa[np]=nq;
                tranc[nq]=tranc[q];
                for(;p&&tranc[p].find(y)!=tranc[p].end()&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
            }
        }last=np;
    }
    map<int,int>::iterator it;
    for(i=1,p=root;i<=n;++i){
        if(i>1)putchar(' ');
        it=tranc[p].begin();
        printf("%d",it->first);
        p=tranc[p][it->first];
    }
 
    return 0;
}