2882: 工艺
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 599 Solved: 268
[Submit][Status][Discuss]
Description
小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏，叫Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。
他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1个方块。如果全都一样，那么这两个工艺品就一样漂亮。
Input
第一行两个整数n，代表方块的数目。
第二行n个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。
Output
一行n个整数，代表最美观工艺品从左到右瑕疵度的值。
Sample Input
10
10 9 8 7 6 5 4 3 2 1
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
Source
求一串数字循环重构后能形成的的最小字典序串。
练习后缀自动机的时候从PoPoQQQ前辈那里看到了这道题，虽然貌似用最小表示法做更合适，但是后缀自动机也可以切。
因为最终不一定（几乎是肯定不会）从一开始给出时的第一个字符开始，为了方便地处理循环问题，我们先将这个串加倍，准确地讲是把1...n-1连接到原串的后面。这样，这个加倍后的串中任意一段长度为n的子串，都是原串的一个合法的循环重构串，我们只需要找到最小的一个长度为n的子串即可，那就后缀自动机喽。
#include <bits/stdc++.h> using namespace std; const int maxn = 6e5 + ; #define it map<int, node*>::iterator /* MYSCANNER */ const int siz = ; inline int get_c(void)
{
static char buf[siz];
static char *head = buf + siz;
static char *tail = buf + siz; if (head == tail)
fread(head = buf, , siz, stdin); return *head++;
} inline int get_i(void)
{
register int ret = ;
register int neg = false;
register int bit = get_c(); for (; bit < ; bit = get_c())
if (bit == '-')neg ^= true; for (; bit > ; bit = get_c())
ret = ret* + bit - ''; return neg ? -ret : ret;
} /* AUTOMATON */ struct node
{
int step;
node *fail;
map<int, node*> next;
node(void)
{
step = ;
fail = NULL;
next.clear();
}
}*root, *last; inline void build(void)
{
root = last = new node;
} inline void extend(int c)
{
node *p = last;
node *t = new node;
t->step = p->step + ;
while (p && !p->next[c])
p->next[c] = t, p = p->fail;
if (p)
{
node *q = p->next[c];
if (q->step == p->step + )
t->fail = q;
else
{
node *k = new node;
k->fail = q->fail;
k->next = q->next;
k->step = p->step + ;
q->fail = t->fail = k;
while (p && p->next[c] == q)
p->next[c] = k, p = p->fail;
}
}
else
t->fail = root;
last = t;
} /* MAIN FUNC */ signed main(void)
{
build();
int n = get_i();
int *s = new int[n + ];
for (int i = ; i <= n; ++i)
s[i] = get_i(), extend(s[i]);
for (int i = ; i < n; ++i)extend(s[i]);
for (node *u = root; n--; )
{
it v = u->next.begin();
printf("%d", v->first);
putchar(n ? ' ' : '\n');
u = v->second;
}
}
@Author: YouSiki