c++设计，给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例 1： 输入：s = "aacecaaa" 输出："aaacecaaa" 示例 2： 输入：s = "abcd" 输出："dcbabcd"

这是一个经典的字符串问题，可以通过 Manacher 算法来解决，时间复杂度为 O(n)。

具体思路如下：

1. 将原字符串翻转得到反转字符串
2. 将原字符串和反转字符串拼接起来，并且在它们中间插入一个特殊字符，比如 #，得到新的字符串 t
3. 对新字符串 t 进行 Manacher 算法，得到每个字符为中心的最长回文半径数组 p
4. 找到最长回文半径 p[len-1]，它表示 t 中以最后一个字符为中心的最长回文半径
5. 截取反转字符串的前缀 len - p[len-1]，并将其拼接到原字符串的前面，得到最短回文串

代码实现如下：