[BZOJ4974][Lydsy1708月赛]字符串大师(KMP)

发布于 2018-03-24  6 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4974][Lydsy1708月赛]字符串大师(KMP)

Description

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

Tag

KMP

解决思路

把我们之前从 Next 推循环节长度的方式反过来。现在给出每一个前缀的最短循环节长度,就相当于给出了 Next。
接下来考虑用 Next 反构造出字典序最小的原串。
其实与构造 Next 的过程很像。向前走到第一个 j+1==Next[i] 的位置,然后就可以知道 str[i] 要与 str[j+1 ]相同。是不是与在构造 KMP 中要求str[j+1]==str[i] 类似?
当然要注意,可能会一直走都头都没有合法位置,那么此时就要找到第一个能够放的字符(字典序最小),为了找到这个字符,需要在跳 Next 的时候在不匹配的时候要标记这个位置不能放的字符。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4974][Lydsy1708月赛]字符串大师(KMP)


HNCJ OIer 一枚