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

以下是 C++ 代码实现：

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.length();
        string r = s;
        reverse(r.begin(), r.end()); // 反转字符串
        string t = s + "#" + r + "#"; // 插入特殊字符
        int m = t.length();
        vector<int> p(m);
        int center = 0, right = 0;
        for (int i = 1; i < m - 1; i++) {
            int j = 2 * center - i;
            if (right > i) {
                p[i] = min(right - i, p[j]);
            }
            while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
                p[i]++;
            }
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        int len = p[m - 2];
        return r.substr(0, n - len) + s;
    }
};

算法的详细解释可以参考我写的博客文章：[LeetCode 214. Shortest Palindrome](https://www.cnblogs.com/grandyang/p/4523624.html)。