题目描述

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

样例1

Input: "aacecaaa"
Output: "aaacecaaa"

样例2

Input: "abcd"
Output: "dcbabcd"

(滚动哈希) $O(n)$

ULL类型的变量溢出等于取模$2^{64}$，p=131或者13331.

C++ 代码

class Solution {
public:
    typedef unsigned long long ULL;
    ULL hash_forward = 0, hash_back = 0, q = 1;
    const int p = 13331;
    string shortestPalindrome(string s) {
        if (!s.size()) return s;
        int pos = 0;
        for(int i = 0; i < s.size(); i ++, q *= p)
        {
            hash_forward = hash_forward * p + s[i];
            hash_back = s[i] * q + hash_back;
            if(hash_forward == hash_back) pos = i;
        }
        auto t = s.substr(pos + 1);
        reverse(t.begin(), t.end());
        return t + s; 
    }
};

KMP $O(n)$

next[i]数组的里存储的是以下标i结尾的字符串中前后缀匹配的最大长度，如图：

C++ 代码

class Solution {
public:
    string shortestPalindrome(string s) {
        string t = s + '#' + string(s.rbegin(), s.rend());
        int n = t.size();
        vector<int> nxt(n, 0);
        int r = 1, len = 0;
        while(r < n)
        {
            if(t[r] == t[len]) nxt[r++] = ++len;
            else
            {
                if(len) len = nxt[len - 1];
                else r++;
            }
        }
        string sub = s.substr(nxt[n - 1]);
        reverse(sub.begin(), sub.end());
        return sub + s;
    }
};

python取巧的方法

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        r = s[::-1]
        for i in range(len(s) + 1):
            if s.startswith(r[i:]):
                return r[:i] + s