BZOJ 4974 [Lydsy1708月赛]字符串大师

题目链接：BZOJ 4974 [Lydsy1708月赛]字符串大师（挂）

算法标签: 字符串、KMP

题目

题目描述

一个串(T)是(S)的循环节，当且仅当存在正整数(k)，使得(S)是(T^k)(即(T)重复(k)次)的前缀，比如(abcd)是(abcdabcdab)的循环节。给定一个长度为(n)的仅由小写字符构成的字符串(S)，请对于每个(k(1le kle n))，求出(S)长度为(k)的前缀的最短循环节的长度(per_i)。字符串大师小Q觉得这个问题过于简单，于是花了一分钟将其AC了，他想检验你是否也是字符串大师。

小Q告诉你(n)以及(per_1,per_2,...,per_n)，请找到一个长度为(n)的小写字符串(S)，使得(S)能对应上(per)。

输入格式

第一行包含一个正整数(n)((1le nle 100000))，表示字符串的长度。

第二行包含(n)个正整数(per_1,per_2,...per_n(1le per_ile i))，表示每个前缀的最短循环节长度。

输入数据保证至少存在一组可行解。

输出格式

输出一行一个长度为(n)的小写字符串(S)，即某个满足条件的(S)。

若有多个可行的(S)，输出字典序最小的那一个。

输入输出样例

输入 #1

5
1 2 2 2 5

输出 #1

ababb

题解：

题解内部分思路和叙述参考https://www.cnblogs.com/GXZlegend/p/7559669.html

一堆废话：

很久没有水题解了，刚好这几天模拟赛，活跃一下博客。

算法：KMP

说道这个算法，如果你深入学习过KMP算法，那么应该会做过这一道题：

POJ-2406 Power Strings

通过研究这道题，我们可以发现对于KMP中(nxt[~])数组的一个性质：

串(S)的最小循环子串（最小循环节）长度为(len - nxt[len])。

这道这个之后再回来重新看这道题，我们会发现，这里用到了这个性质，只不过是你逆序的，所以我们就可以通过所给的循环节长度直接得到(nxt[1] sim nxt[len])。

for (int i = 1, x; i <= n; i ++ ) {
	scanf("%d", &x);
	nxt[i] = i - x;
}

这样的话我们就直接按照KMP的过程进行逆序模拟：

如果(nxt[i] eq 0)，那么就可以在(i)之前的部分中找到(s[nxt[i]])。
如果(nxt[i] = 0)，根据KMP的过程，对于一个匹配位置，如果它的下一个字符和它不相等，那么我们就跳到当前的(nxt)位置，一直到(nxt=-1)为止，之后当前位置的(nxt[i])就等于匹配到的(nxt + 1)，这样反复而处理出(nxt[~])数组。

那么如果当前状态是(nxt[i] = 0)的完全失配状态，每一次匹配到的位置上的字符都应该与当前字符失配。这样我们可以记录所有在匹配位置的字符，找到第一个没有出现的字符放到当前位置上即可。

Tips：对于记录所有出现过的匹配位置字符，我们可以选择(STL-set)直接去重和维护有序，也可以通过按照每一位的间戳进行标记，再扫26个字母找到第一个没有出现过的即可。（由于题目保证有解）

for (int j = nxt[i - 1]; ~j; j = nxt[j]) {
	vis[str[j + 1] - 'a'] = i;
}
for (int j = 0; j < 26; j ++ ) {
	if (vis[j] != i) {
		tmp = j;
		break ;
	}
}
str[i] = tmp + 'a';

AC代码

#include <bits/stdc++.h>

using namespace std;

#define setI(x) freopen(x".in", "r", stdin);

#define setO(x) freopen(x".out", "w", stdout);

#define setIO(x) setI(x) setO(x);

int nxt[100010];

int n, x, tmp;

int vis[100010];

char str[100010];

int main() {
// setIO("meaning")
	scanf("%d", &n);
	nxt[0] = -1;
	for (int i = 1; i <= n; i ++ ) {
		scanf("%d", &x);
		nxt[i] = i - x;
		if (nxt[i]) {
			str[i] = str[nxt[i]];
			continue ;
		}
		for (int j = nxt[i - 1]; ~j; j = nxt[j]) {
			vis[str[j + 1] - 'a'] = i;
		}
		for (int j = 0; j < 26; j ++ ) {
			if (vis[j] != i) {
				tmp = j;
				break ;
			}
		}
		str[i] = tmp + 'a';
	}
	printf("%s
", str + 1);
	return 0;
}