BZOJ4974【Lydsy201708月赛】字符串大师

Problem

【Lydsy1708月赛】字符串大师

Description

一个串是的循环节，当且仅当存在正整数，使得是重复次的前缀，比如abcd是abcdabcdab的循环节。
给定一个长度为的仅由小写字符构成的字符串，请对于每个，求出长度为的前缀的最短循环节的长度。
字符串大师觉得这个问题过于简单，于是花了一分钟将其了，他想检验你是否也是字符串大师。
告诉你以及，请找到一个长度为的小写字符串，使得能对应上。

Input

第一行包含一个正整数，表示字符串的长度。
第二行包含个正整数，表示每个前缀的最短循环节长度。
输入数据保证至少存在一组可行解。

Output

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

Sample Input

5
1 2 2 2 5

Sample Output

ababb

Source

Claris原创，本版权所有，翻版必究

标签：KMP 贪心 构造

Solution

好题。

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

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

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

将末尾循环节长度那么长去掉，得到，将第一个循环节去掉，得到，发现两者是相同的（如下图）。而这显然是的，所以的末尾位置为，即

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

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

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

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;
}