BZOJ4974【Lydsy月赛201708】字符串大师

Problem

【Lydsy1708月赛】字符串大师


Description

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

Input

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

Output

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

Sample Input

1
2
5
1 2 2 2 5

Sample Output

1
ababb

Source

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

标签:KMP 贪心 构造

Solution

好题。

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

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


1.PNG

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


2.PNG

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


3.PNG

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

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}
------------- Thanks For Reading -------------
0%