看上去比較SA，但是在學(xué)SAM所以就用SAM來(lái)做……
把串復(fù)制一遍接在后面，對(duì)這個(gè)新串求SAM（這里的兒子節(jié)點(diǎn)要用map轉(zhuǎn)移），然后從根節(jié)點(diǎn)每次都向最小的轉(zhuǎn)移走，這樣走n次轉(zhuǎn)移的串就是答案

#include<iostream> #include<cstdio> #include<map> using namespace std; const int N=1000005; int n,a[N],fa[N],dis[N],la,cur=1,cnt=1; map<int,int>ch[N]; int read() {int r=0,f=1;char p=getchar();while(p>'9'||p<'0'){if(p=='-')f=-1;p=getchar();}while(p>='0'&&p<='9'){r=r*10+p-48;p=getchar();}return r*f; } void ins(int c,int id) {la=cur,dis[cur=++cnt]=id;int p=la;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=cur;if(!p)fa[cur]=1;else{int q=ch[p][c];if(dis[q]==dis[p]+1)fa[cur]=q;else{int nq=++cnt;dis[nq]=dis[p]+1;// memcpy(ch[nq],ch[q],sizeof(ch[nq]));for(map<int,int>::iterator it=ch[q].begin();it!=ch[q].end();it++)ch[nq][it->first]=it->second;fa[nq]=fa[q];fa[q]=fa[cur]=nq;for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;}} } int main() {n=read();for(int i=1;i<=n;i++)a[i]=a[i+n]=read();for(int i=1;i<=2*n;i++)ins(a[i],i);for(int i=1,nw=1;i<=n;i++){printf("%d ",ch[nw].begin()->first);nw=ch[nw].begin()->second;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lokiii/p/10000966.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 2882: 工艺【SAM】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。