luogu#P9211. 「不死鸟附体」

「不死鸟附体」

题目背景

死而复生,生而复死。所谓的不死鸟就是这样的一种生物,在无尽的时间里无尽地循环往复。

果然最好还是别获得不老不死的能力吧。

题目描述

不死鸟的「一生」可以被看成一个长度不超过 lmaxl_{\max} 的字符串 S0S_0。在无尽的轮回后形成了一个无限长的字符串 Sinf=S0+S0+S0+S_{\mathrm{inf}}=S_0+S_0+S_0+\cdots。现在截取 SS_{\infty}ll 个字符,作为可观测时间里不死鸟的生命 SfinS_{\mathrm{fin}}

然而所谓的轮回并不是机械的循环往复。因此,SfinS_\mathrm{fin} 当中会有不超过 nn 个字符被修改成了别的字符,变成了 SrealS_{\mathrm{real}}

现在观测到了 SrealS_{\mathrm{real}},我们希望找到这轮回的最小片段 S0S_0

当然,由于 SrealS_{\mathrm{real}}SfinS_{\mathrm{fin}} 修改而来,可能不存在长度不超过 lmaxl_{\max} 的字符串 S0S_0 可以直接生成 SrealS_{\mathrm{real}}。于是,现在只希望找到这样一个 S0S_0',使得由它生成的 SfinS_\mathrm{fin}' 修改不超过 mm 个字符后可以变成 SrealS_{\mathrm{real}}

输入格式

第一行有四个正整数 l,lmax,n,ml,l_{\max},n,m

第二行描述观测到的长度为 ll 的字符串 SrealS_{\mathrm{real}}

输出格式

第一行输出一个正整数 l0l_0,表示你所找到的 S0S_0 的长度。你应当保证 1l0lmax1\le l_0\le l_{\max}

第二行输出一个长度为 l0l_0 的字符串 S0S_0,表示你所找到的字符串。

25 8 5 10
aaacdaabbbaabccaabcdaabcd

5
aaacd

提示

样例解释

重要:样例仅供理解题意,不一定符合数据范围的约束。具体约束请参见「数据范围及约定」。

生成 SrealS_{\mathrm{real}} 所用的 S0=aabcdS_0=\verb!aabcd!

  • 由此生成 $S_{\mathrm{inf}}=\verb!aabcdaabcdaabcdaabcdaabcd!\cdots$;
  • 由此生成 Sfin=aabcdaabcdaabcdaabcdaabcdS_{\mathrm{fin}}=\verb!aabcdaabcdaabcdaabcdaabcd!
  • 由此生成 $S_{\mathrm{real}\kern{-2.5pt}}=\verb!aaacdaabbbaabccaabcdaabcd!$。

样例输出给出了一个可能的 S0=aaacdS_0'=\verb!aaacd!。由此计算出 SfinS_{\mathrm{fin}}'SrealS_{\mathrm{real}} 的差距:

$$\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}$$

相差为 77,不超过 m=10m=10,可以被接受。

数据范围及约定

对于全部数据,保证 l=3×105l=3\times 10^5n=3×103n=3\times 10^3m=104m=10^41lmax1051\le l_{\max} \le 10^5