luogu#P9211. 「不死鸟附体」
「不死鸟附体」
题目背景
死而复生,生而复死。所谓的不死鸟就是这样的一种生物,在无尽的时间里无尽地循环往复。
果然最好还是别获得不老不死的能力吧。
题目描述
不死鸟的「一生」可以被看成一个长度不超过 的字符串 。在无尽的轮回后形成了一个无限长的字符串 。现在截取 前 个字符,作为可观测时间里不死鸟的生命 。
然而所谓的轮回并不是机械的循环往复。因此, 当中会有不超过 个字符被修改成了别的字符,变成了 。
现在观测到了 ,我们希望找到这轮回的最小片段 。
当然,由于 从 修改而来,可能不存在长度不超过 的字符串 可以直接生成 。于是,现在只希望找到这样一个 ,使得由它生成的 修改不超过 个字符后可以变成 。
输入格式
第一行有四个正整数 。
第二行描述观测到的长度为 的字符串 。
输出格式
第一行输出一个正整数 ,表示你所找到的 的长度。你应当保证 。
第二行输出一个长度为 的字符串 ,表示你所找到的字符串。
25 8 5 10
aaacdaabbbaabccaabcdaabcd
5
aaacd
提示
样例解释
重要:样例仅供理解题意,不一定符合数据范围的约束。具体约束请参见「数据范围及约定」。
生成 所用的 。
- 由此生成 $S_{\mathrm{inf}}=\verb!aabcdaabcdaabcdaabcdaabcd!\cdots$;
- 由此生成 ;
- 由此生成 $S_{\mathrm{real}\kern{-2.5pt}}=\verb!aaacdaabbbaabccaabcdaabcd!$。
样例输出给出了一个可能的 。由此计算出 与 的差距:
$$\begin{aligned} S_{\mathrm{fin}}'=&\texttt{aaacdaa\textcolor{red}a\textcolor{red}c\textcolor{red}daa\textcolor{red}ac\textcolor{red}daa\textcolor{red}acdaa\textcolor{red}acd}\cr S_{\mathrm{real}}=&\texttt{aaacdaabbbaabccaabcdaabcd}\cr \end{aligned}$$相差为 ,不超过 ,可以被接受。
数据范围及约定
对于全部数据,保证 ,,,。