[NICA #2] 字符串入门题

Luogu

IDLGB3829

Time1000ms

Memory512MB

DifficultyP2

字符串贪心Special JudgeO2优化

给定一个仅包含大小写字母和数字的字符串 $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$ 的一个可以为空的前缀以及一个可以为空的后缀后得到 $s$。 ## Input 第一行两个正整数 $n,k$，其中 $n$ 是 $s$ 的长度。第二行一个字符串 $s$，仅包含大小写字母和数字。 ## Output 如果不存在这样的拆分方案，输出 `-1` 。否则第一行输出一个正整数 $t(t\ge k)$，表示你要把 $s$ 拆分成 $t$ 个字符串。接下来 $t$ 行，每行一个字符串，第 $i$ 行表示 $s_i$。你需要保证 $s_1s_2\dots s_t=s$。 [samples] ## Background 小波说这是字符串入门题极好的，所以这是极好的。 ## Note #### 样例 1 解释 `1145|14`是一种合法的拆分方案，因为拆分出了 $2$ 个字符串且 $2\ge k$，并且`14`是`1145`的一个子串。 #### 样例 2 解释 `a1A|a1|1Aa`是一种合法的拆分方案，因为拆分出了 $3$ 个字符串且 $3\ge k$，并且`a1`是`a1A`的一个子串，且`1Aa`是`a1Aa1`的一个子串。 #### 样例 3 解释尝试所有拆分方案后发现无论如何拆分都无法满足条件。 #### 数据范围对于所有数据，满足 $2\le k\le n\le 10^6$，$s$ 仅由大小写字母和数字构成。

Samples

Input #1

6 2
114514

Output #1

2
1145
14

Input #2

8 2
a1Aa11Aa

Output #2

3
a1A
a1
1Aa

Input #3

11 2
stoImakforz

Output #3

-1

API Response (JSON)

{
  "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$ 的一个可以为空的前缀以及一个可以...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments