{"problem":{"name":"「不死鸟附体」","description":{"content":"不死鸟的「一生」可以被看成一个长度不超过 $l_{\\max}$ 的字符串 $S_0$。在无尽的轮回后形成了一个无限长的字符串 $S_{\\mathrm{inf}}=S_0+S_0+S_0+\\cdots$。现在截取 $S_{\\mathrm{inf}}$ 前 $l$ 个字符，作为可观测时间里不死鸟的生命 $S_{\\mathrm{fin}}$。 然而所谓的轮回并不是机械死板的循环往复。因此，$S_\\ma","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9211"},"statements":[{"statement_type":"Markdown","content":"不死鸟的「一生」可以被看成一个长度不超过 $l_{\\max}$ 的字符串 $S_0$。在无尽的轮回后形成了一个无限长的字符串 $S_{\\mathrm{inf}}=S_0+S_0+S_0+\\cdots$。现在截取 $S_{\\mathrm{inf}}$ 前 $l$ 个字符，作为可观测时间里不死鸟的生命 $S_{\\mathrm{fin}}$。\n\n然而所谓的轮回并不是机械死板的循环往复。因此，$S_\\mathrm{fin}$ 当中会有**不超过 $n$ 个字符**被修改成了别的字符，变成了 $S_{\\mathrm{real}}$。\n\n现在观测到了 $S_{\\mathrm{real}}$，我们希望找到这轮回的周期 $S_0$。然而由于不死鸟的轮回太过漫长，我们只希望找到这样一个 $S_0'$，使得由它生成的 $S_\\mathrm{fin}'$ 修改**不超过 $m$ 个字符**后就可以变成 $S_{\\mathrm{real}}$。\n\n## Input\n\n第一行有四个正整数 $l,l_{\\max},n,m$。\n\n第二行描述观测到的长度为 $l$ 的字符串 $S_{\\mathrm{real}}$。\n\n## Output\n\n第一行输出一个正整数 $l_0$，表示你所找到的 $S_0$ 的长度。你应当保证 $1\\le l_0\\le l_{\\max}$。\n\n第二行输出一个长度为 $l_0$ 的字符串 $S_0$，表示你所找到的字符串。\n\n[samples]\n\n## Background\n\n死而复生，生而复死。所谓的不死鸟就是这样的一种生物，在无尽的时间里无尽地循环往复。\n\n果然最好还是别获得不老不死的能力吧。\n\n## Note\n\n### 样例解释\n\n样例仅供理解题意，**不符合数据范围的约束**。具体约束请参见「数据范围及约定」。\n\n生成 $S_{\\mathrm{real}}$ 所用的 $S_0=\\verb!aabcd!$。\n\n- 由此生成 $S_{\\mathrm{inf}}=\\verb!aabcdaabcdaabcdaabcdaabcd!\\cdots$；\n- 由此生成 $S_{\\mathrm{fin}}=\\verb!aabcdaabcdaabcdaabcdaabcd!$；\n- 由此生成 $S_{\\mathrm{real}\\kern{-2.5pt}}=\\verb!aaacdaabbbaabccaabcdaabcd!$。\n\n样例输出给出了一个可能的 $S_0'=\\verb!aaacd!$。由此计算出 $S_{\\mathrm{fin}}'$ 与 $S_{\\mathrm{real}}$ 的差距：\n\n$$\\begin{aligned}\nS_{\\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\nS_{\\mathrm{real}}=&\\texttt{aaacdaabbbaabccaabcdaabcd}\\cr\n\\end{aligned}$$\n\n相差为 $7$，不超过 $m=10$，可以被接受。\n\n### 数据范围及约定\n\n对于全部数据，保证 $l=3\\times 10^5$，$n=3\\times 10^3$，$m=10^4$，$1\\le l_{\\max} \\le 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9211","tags":["字符串","Special Judge","随机化","传智杯"],"sample_group":[["25 8 5 10\naaacdaabbbaabccaabcdaabcd\n","5\naaacd"]],"created_at":"2026-03-03 11:09:25"}}