BZOJ4974【Lydsy201708月赛】字符串大师

Problem

【Lydsy1708月赛】字符串大师

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

一个串$T$是$S$的循环节，当且仅当存在正整数$k$，使得$S$是$T$重复$k$次的前缀，比如abcd是abcdabcdab的循环节。
给定一个长度为$n$的仅由小写字符构成的字符串$S$，请对于每个$k\;(1\le k\le n)$，求出$S$长度为$k$的前缀的最短循环节的长度$per_i$。
字符串大师$\mathrm{小Q}$觉得这个问题过于简单，于是花了一分钟将其$\mathrm{AC}$了，他想检验你是否也是字符串大师。
$\mathrm{小Q}$告诉你$n$以及$per_1,per_2,\cdots,per_n$，请找到一个长度为$n$的小写字符串$S$，使得$S$能对应上$per$。

Input

第一行包含一个正整数$n\;(1\le n\le10^5)$，表示字符串的长度。
第二行包含$n$个正整数$per_1,per_2,\cdots,per_n\;(1\le per_i\le i)$，表示每个前缀的最短循环节长度。
输入数据保证至少存在一组可行解。

Output

输出一行一个长度为$n$的小写字符串$S$，即某个满足条件的$S$。
若有多个可行的$S$，输出字典序最小的那一个。

Sample Input

5
1 2 2 2 5

Sample Output

ababb

Source

Claris原创，本$\mathrm{OJ}$版权所有，翻版必究

标签：KMP 贪心 构造

Solution

$\mathrm{KMP}$好题。

$\bigstar$本文中所有数组和字符串下标从$0$开始。

首先有一个结论：$nxt_i=i-per_i$
证明：
对于字符串$P$，其最短循环节为$R$，除去循环节后多余的部分为$Q$，如图所示。


那么再在上面接一个$R$，一定可以包含$P$，于是可以知道$Q$一定是$R$的前缀，所以有下图：


将$P$末尾循环节长度那么长去掉，得到$P_1$，将$P$第一个循环节去掉，得到$P_2$，发现两者是相同的（如下图）。而这显然是$P$的$boarder$，所以$P_1$的末尾位置为$n-per$，即$nxt[n]=n-per$


这样根据给出的$per$可以将$nxt$数组处理出来。
从前往后构造，对于位置$i$：

• $nxt_i\ne-1$，一定有$s[i]=s[nxt_i]$，可以直接赋值
• $nxt_i=-1$，那么在计算$nxt$的过程中，即将这个串与自己做匹配的时候，不断根据$nxt$向前跳到的位置一定不会和当前位置匹配，否则$nxt_i=最先能匹配的位置$。于是将能向前跳到的位置上的字符存下来，找一个最小的没有跳到过的字符作为这一位置的字符

如此贪心构造即可得到最优解。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, nxt[MAX_N+5], s[MAX_N+5]; bool mrk[26];
int main() {
    read(n);
    for (int i = 0; i < n; i++) read(nxt[i]), nxt[i] = i-nxt[i];
    for (int p = 1; p < n; p++) {
        if (~nxt[p]) s[p] = s[nxt[p]];
        else {
            memset(mrk, false, sizeof mrk);
            for (int q = nxt[p-1]; ~q; q = nxt[q])
                mrk[s[q+1]] = true;
            for (int c = 1; c < 26; c++)
                if (!mrk[c]) {s[p] = c; break;}
        }
    }
    for (int i = 0; i < n; i++) printf("%c", 'a'+s[i]);
    return 0;
}