CF594E Cutting the Line

给定一个非空字符串 $s$ 和一个整数 $k$。对该字符串恰好执行一次如下操作： - 将字符串 $s$ 最多划分为 $k$ 个非空子串，即将 $s$ 表示为 $s = t_1 + t_2 + \ldots + t_m$，其中 $1 \leq m \leq k$。 - 可以将某些 $t_i$ 替换为其逆序字符串 $t_i^r$，即从右到左的表示。 - 按原顺序重新连接这些字符串，得到 $s' = t'_1 t'_2 \ldots t'_m$，其中 $t'_i$ 可以是 $t_i$ 或 $t_i^r$。 你的任务是确定经过上述操作后，按字典序排列可以得到的最小的字符串 $s'$。

第一行输入字符串 $s$（$1 \leq |s| \leq 5000000$），只含有小写英文字母。 第二行输入整数 $k$（$1 \leq k \leq |s|$），表示最多可以划分成的部分数。

输出经过操作后按字典序最小的字符串 $s'$。

由 ChatGPT 5 翻译