【BZOJ2882】工艺

Description

小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏,叫Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的,而且由于机器的要求,他们只能做到把这个工艺品最左边的方块放到最右边。
他们想,在仅这一个操作下,最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是,从头开始比较,如果第i个位置上方块不一样那么谁的瑕疵度小,那么谁就更漂亮,如果一样那么继续比较第i+1个方块。如果全都一样,那么这两个工艺品就一样漂亮。

Input

第一行两个整数n,代表方块的数目。
第二行n个整数,每个整数按从左到右的顺序输出方块瑕疵度的值。

Output

一行n个整数,代表最美观工艺品从左到右瑕疵度的值。

Sample Input

10 10 9 8 7 6 5 4 3 2 1

Sample Output

1 10 9 8 7 6 5 4 3 2

HINT

【数据规模与约定】
对于20%的数据,n<=1000
对于40%的数据,n<=10000
对于100%的数据,n<=300000

题解:其实Spoj8222才是我后缀自动机的第一题,但是网太差,不想写博客了~

看题目描述一定是让你将原串倍长一遍在搞一搞(或者是&*¥%最小表示法),本题要求的东西比较简单,就是让你把倍长后的串扔到SAM里跑一遍就行了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
const int maxn=1200010;
int n,tot,last,maxx;
int pre[maxn],st[maxn],dep[maxn],r[maxn],tb[maxn];
int v[maxn];
map<int,int> ch[maxn];
void add(int x)
{
int p=last,np=++tot;
last=np,dep[np]=dep[p]+1;
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np;
if(!p) pre[np]=1;
else
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) pre[np]=q;
else
{
int nq=++tot;
dep[nq]=dep[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq,ch[nq]=ch[q];
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq;
}
}
}
int main()
{
tot=last=1;
scanf("%d",&n);
int i,p;
for(i=1;i<=n;i++) scanf("%d",&v[i]),v[i+n]=v[i];
for(i=1;i<=n*2;i++) add(v[i]);
for(i=p=1;i<=n;i++)
{
printf("%d",ch[p].begin()->first),p=ch[p].begin()->second;
if(i<n) printf(" ");
}
return 0;
}
05-11 21:45