CF2004G.Substring Compression

我们定义对一个由至少 $2$ 个 $1$ 到 $9$ 的数字组成的字符串 $t$ 的压缩操作如下：

• 将其分割为偶数个非空子串——设这些子串为 $t_1, t_2, \dots, t_m$（因此 $t = t_1 + t_2 + \dots + t_m$，其中 $+$ 表示连接操作）；
• 写下字符串 $t_2$ 共 $t_1$ 次，然后写下字符串 $t_4$ 共 $t_3$ 次，依此类推。

例如，对于字符串 "12345"，可以这样分割：("1", "23", "4", "5")，然后写下 "23" 共 $1$ 次，"5" 共 $4$ 次，得到 "235555"。

定义函数 $f(t)$，表示对字符串 $t$ 进行上述操作后，能够得到的最短字符串长度。

给定一个由 $n$ 个 $1$ 到 $9$ 的数字组成的字符串 $s$，以及一个整数 $k$。请计算 $s$ 的所有长度恰好为 $k$ 的连续子串的 $f$ 值。

第一行包含两个整数 $n$ 和 $k$（$2 \le k \le n \le 2 \cdot 10^5$）。

第二行包含字符串 $s$（$|s| = n$），仅由 $1$ 到 $9$ 的数字组成。

输出 $n - k + 1$ 个整数，分别表示 $f(s_{1,k}), f(s_{2,k+1}), \dots, f(s_{n - k + 1, n})$。

由 ChatGPT 4.1 翻译