bzoj 2882: 工艺【SAM】

看上去比较SA，但是在学SAM所以就用SAM来做……

把串复制一遍接在后面，对这个新串求SAM（这里的儿子节点要用map转移），然后从根节点每次都向最小的转移走，这样走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;

}

巴特西

bzoj 2882: 工艺【SAM】

最新文章

热门文章