{"problem":{"name":"[NICA #2] 字符串入门题","description":{"content":"给定一个仅包含大小写字母和数字的字符串 $s$，问能否将 $s$ 拆分成至少 $k$ 个子串 $s_1,s_2,\\dots,s_t(t\\ge k)$ 满足 $\\forall 1<i\\le t$ 有 $s_i$ 是 $s_1s_2\\dots s_{i-1}$（这里表示的是拼接）的子串。 一个字符串 $s$ 是另一个字符串 $t$ 的子串当且仅当可以通过删除 $t$ 的一个可以为空的前缀以及一个可以","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3829"},"statements":[{"statement_type":"Markdown","content":"给定一个仅包含大小写字母和数字的字符串 $s$，问能否将 $s$ 拆分成至少 $k$ 个子串 $s_1,s_2,\\dots,s_t(t\\ge k)$ 满足 $\\forall 1<i\\le t$ 有 $s_i$ 是 $s_1s_2\\dots s_{i-1}$（这里表示的是拼接）的子串。\n\n一个字符串 $s$ 是另一个字符串 $t$ 的子串当且仅当可以通过删除 $t$ 的一个可以为空的前缀以及一个可以为空的后缀后得到 $s$。\n\n## Input\n\n第一行两个正整数 $n,k$，其中 $n$ 是 $s$ 的长度。\n\n第二行一个字符串 $s$，仅包含大小写字母和数字。\n\n## Output\n\n如果不存在这样的拆分方案，输出 `-1` 。\n\n否则第一行输出一个正整数 $t(t\\ge k)$，表示你要把 $s$ 拆分成 $t$ 个字符串。\n\n接下来 $t$ 行，每行一个字符串，第 $i$ 行表示 $s_i$。你需要保证 $s_1s_2\\dots s_t=s$。\n\n[samples]\n\n## Background\n\n小波说这是字符串入门题极好的，所以这是极好的。\n\n## Note\n\n#### 样例 1 解释\n\n`1145|14`是一种合法的拆分方案，因为拆分出了 $2$ 个字符串且 $2\\ge k$，并且`14`是`1145`的一个子串。\n\n#### 样例 2 解释\n\n`a1A|a1|1Aa`是一种合法的拆分方案，因为拆分出了 $3$ 个字符串且 $3\\ge k$，并且`a1`是`a1A`的一个子串，且`1Aa`是`a1Aa1`的一个子串。\n\n#### 样例 3 解释\n\n尝试所有拆分方案后发现无论如何拆分都无法满足条件。\n\n#### 数据范围\n\n对于所有数据，满足 $2\\le k\\le n\\le 10^6$，$s$ 仅由大小写字母和数字构成。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3829","tags":["字符串","贪心","Special Judge","O2优化"],"sample_group":[["6 2\n114514","2\n1145\n14"],["8 2\na1Aa11Aa","3\na1A\na1\n1Aa"],["11 2\nstoImakforz","-1"]],"created_at":"2026-03-03 11:09:25"}}