CF137D Palindromes

星期五是 Polycarpus 最喜欢的一天。这不仅仅是因为星期五之后就是周末，更因为星期五的课程安排是：2 节信息技术课、2 节数学课和 2 节文学课。当然，Polycarpus 对所有课程都做好了准备，但他的朋友 Innocentius 却不是这样。Innocentius 整个晚上都在玩他最喜欢的游戏 Fur2，结果没有时间完成文学作业。为了不被打 F，Innocentius 决定在信息技术课和数学课上补做文学作业并阅读名为《Storm and Calm》的书（这些科目他一向没问题）。当信息技术老师 Watkins 先生发现后，决定给 Innocentius 额外的任务，让他更加专注于课堂内容，而不是与信息技术无关的事情。 Watkins 先生说，回文串是指从左到右和从右到左读都相同的字符串。字符串 $a$ 和 $b$ 的连接是指将字符串 $b$ 紧接在字符串 $a$ 后面得到的新字符串 $ab$。当然，Innocentius 早就知道这些知识，但这次的任务比他想象的要难得多。Watkins 先生要求他将《Storm and Calm》的文本最少修改多少个字符，使得整本书的文本也可以表示为不超过 $k$ 个回文串的连接。Innocentius 完成不了这个任务，因此请求你帮忙。

第一行输入一个非空字符串 $s$，表示《Storm and Calm》的文本（不含空格）。字符串 $s$ 的长度不超过 $500$ 个字符。$s$ 仅由大写和小写拉丁字母组成。第二行输入一个整数 $k$，满足 $1 \leq k \leq |s|$，其中 $|s|$ 表示字符串 $s$ 的长度。

第一行输出 Innocentius 需要修改的最少字符数。第二行输出一个由不超过 $k$ 个回文串连接而成的字符串。每两个相邻的回文串之间用字符“+”（ASCII 码 43）分隔。每个回文串都不能为空，且仅由大写和小写拉丁字母组成。如果存在多种方案，输出任意一种均可。 字母的大小写敏感，即大写字母与对应的小写字母不同。

由 ChatGPT 4.1 翻译