题目描述

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

样例

输入: "aacecaaa"
输出: "aaacecaaa"

输入: "abcd"
输出: "dcbabcd"

算法

(贪心，KMP) $O(n)$

1. 求字符串 s 的最长回文前缀，然后剩余的部分就可以逆序拼接到 s 的最前边得到一个回文串。例如 abcbabcab 的最长回文前缀是 abcba，则答案就是 bacb + abcba + bcab = bacbabcbabcab。
2. 首先将原串逆序复制一份，得到字符串 t。
3. 将 s + # + t 作为新字符串，求其 next 数组。
4. 假设下标从 0 开始，则最后位置上的 next 值加 1 就是最长回文前缀的长度，假设重合长度为 l。
5. 最终答案为 t[0:l] + s。

时间复杂度

• KMP 的时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储逆串和 next 数组。

C++ 代码

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        string t(s.rbegin(), s.rend());
        string str(s + "#" + t);

        vector<int> nxt(2 * n + 1);

        int j = -1;
        nxt[0] = -1;

        for (int i = 1; i < 2 * n + 1; i++) {
            while (j > -1 && str[j + 1] != str[i]) j = nxt[j];
            if (str[j + 1] == str[i])
                j++;

            nxt[i] = j;
        }

        return t.substr(0, n - nxt[2 * n] - 1) + s;
    }
};