SP6957 PARTPAL - Partial Palindrome

费尔南多是一个叫回文国的国家的总统。在回文国，每两年会举行一次特别的选举，过程如下： - 不是总统的候选人提供一个字符串 **_O_**（仅由大写字母和字符 '?' 组成）、一个字符串 **_U_**（仅由大写字母组成），以及一个整数 **_K_**。 - 现任总统有一天的时间，根据以下规则寻找字符串 **_O_** 中的最长回文串： - 将 **_O_** 中每个 `?` 替换为 **_U_** 中对应位置的字母，即第 _**i**_ 个 `?` 替换为 **_U_** 的第 _**i**_ 个字母。 - 每次寻找回文串时，他可以选择替换一些 `?` 为任意字母，最多可替换 _**K**_ 次。 - 如果他找到一个回文串，就重新开始第一步。 - 如果他没有找到回文串，那么这个候选人就会成为新总统。 - 如果还有其他候选人，则重新进行选举。 费尔南多希望能继续连任两年，因此他需要你编写一个程序帮助他完成这一挑战。

第一行输入一个字符串 **_O_**（1 ≤ **_O_** 的长度 ≤ 5 × 10⁵），这个字符串是费尔南多需要计算的，以便继续连任。字符串中只会出现大写字母和字符 '?'，并且至少有一个 '?'。 第二行输入的字符串 **_U_** 提供了替换 `?` 的指引，其中的字母对应替换 **_O_** 中的 `?`。**_U_** 仅由大写字母组成。 第三行输入一个整数 **_K_**（0 ≤ **_K_** ≤ 300），表示可以替换的最大次数。 保证字符串 **_O_** 中的 `?` 不超过 300 个。

第一行输出一个整数 **_S_**，表示可以找到的最长回文串的长度。 随后每一行输出一个最长回文串 **_P_i_** 及其在 **_O_** 中的起始位置 **_L_i_**。每个 **_P_i_** 都只包含大写字母。 **注意：** - 所有最长的回文串必须按字典序递增排列进行输出。 - 如果两个或多个回文串从相同位置开始，则只需输出其中之一。 **本翻译由 AI 自动生成**