214. Shortest Palindrome

rolling hash O(n) time O(n) space

class Solution {
public:
    string shortestPalindrome(const string &s) {
        if (s.empty()) return s;
        string r(rbegin(s), rend(s));
        long M = INT_MAX, B = 256;
        int n = size(s);
        vector<long> p(n, 1);
        for (int i = 1; i < n; ++i) {
            p[i] = (p[i - 1] * B) % M;
        }
        long sh = 0, rh = 0;
        for (int i = 0; i < n; ++i) {
            sh = (sh * B + s[i]) % M;
            rh = (rh * B + r[i]) % M;
        }
        if (sh == rh && s.compare(0, n, r, 0, n) == 0) return s;
        for (int i = 1; i < n; ++i) {
            sh = (sh + M - s[n - i] * p[i - 1] % M) % M;
            rh = (rh + M - r[i - 1] * p[n - i] % M) % M;
            if (sh == rh * p[i] % M && s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s;
        }
        return s;
    }
};

class Solution {
public:
    string shortestPalindrome(const string &s) {
        if (s.empty()) return s;
        string r(rbegin(s), rend(s));
        long M = INT_MAX, B = 256;
        int n = size(s);
        vector<long> p(n, 1);
        for (int i = 1; i < n; ++i) {
            p[i] = (p[i - 1] * B) % M;
        }
        long sh = 0, rh = 0;
        for (int i = 0; i < n; ++i) {
            sh = (sh + s[i] * p[i]) % M;
            rh = (rh + r[i] * p[i]) % M;
        }
        if (sh == rh && s.compare(0, n, r, 0, n) == 0) return s;
        for (int i = 1; i < n; ++i) {
            sh = (sh + M - s[n - i] * p[n - i] % M) % M;
            rh = (rh + M - r[i - 1] * p[i - 1] % M) % M;
            if ((sh * p[i]) % M == rh && s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s;
        }
        return s;
    }
};

class Solution {
public:
    string shortestPalindrome(const string &s) {
        if (s.empty()) return s;
        string r(rbegin(s), rend(s));
        long M = INT_MAX, B = 256;
        int n = size(s);
        vector<long> p(n, 1), sh(n), rh(n);
        for (int i = 1; i < n; ++i) {
            p[i] = (p[i - 1] * B) % M;
        }
        sh[0] = s[0];
        rh[0] = r[0];
        for (int i = 1; i < n; ++i) {
            sh[i] = (sh[i - 1] + s[i] * p[i]) % M;
            rh[i] = (rh[i - 1] + r[i] * p[i]) % M;
        }
        if (sh[n - 1] == rh[n - 1] && s.compare(0, n, r, 0, n) == 0) return s;
        for (int i = 1; i < n; ++i) {
            auto a = (sh[n - i - 1] * p[i]) % M;
            auto b = (rh[n - 1] + M - rh[i - 1]) % M;
            if (a == b && s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s;
        }
        return s;
    }
};

O(n²)递归版
KMP可以实现O(n)
我们使用双指针来找出字符串s的最长回文前缀的大概范围，指针i和j分别指向s串的开头和末尾，若 s[i] 和 s[j] 相等，则i自增1，j自减1，否则只有j自减1。这样遍历一遍后，最长回文前缀就在范围 [0, i) 中，但不保证这个本身就是最大回文前缀，我们只能确定后面剩余的部分肯定不属于，此时我们提取出剩下的字符，翻转一下加到最前面，而对范围 [0, i) 内的子串再次递归调用本函数，这样，在子函数最终会组成最短的回文串，从而使得整个的回文串就是最短的
Each iteration of shortestPalindrome is linear in size of substring and the maximum number of recursive calls can be n/2 times as shown in the Intuition section.
Let the time complexity of the algorithm be T(n). Since, at the each step for the worst case, the string can be divide into 2 parts and we require only one part for further computation. Hence, the time complexity for the worst case can be represented as : T(n)=T(n-2)+O(n)T(n)=T(n−2)+O(n). So, T(n) = O(n) + O(n-2) + O(n-4) + … + O(1)T(n)=O(n)+O(n−2)+O(n−4)+…+O(1) which is O(n²)

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.length();
        int i = 0;
        for (int j = n - 1; j >= 0;--j) {
            if (s[i] == s[j]) {
                ++i;
            }
        }
        if (i == n) return s;
        string prefix = s.substr(i);
        reverse(prefix.begin(), prefix.end());
        string mid = shortestPalindrome(s.substr(0, i));
        return prefix + mid + s.substr(i);
    }
};

iterative O(n²) time

class Solution {
public:
    string shortestPalindrome(const string &s) {
        int n = size(s);
        string r(rbegin(s), rend(s));
        for (int i = 0; i < n; ++i) {
            if (s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s; // 避免copy
        }
        return s;
    }
};

TLE O(n²) time

class Solution {
public:
    string shortestPalindrome(const string &s) {
        int n = size(s);
        string r(rbegin(s), rend(s));
        for (int i = 0; i < n; ++i) {
            if (s.substr(0, n - i) == r.substr(i)) return r.substr(0, i) + s;
        }
        return s;
    }
};

错误dp版本O(n²) time O(n²) space
题目要求只能在前面加，这个版本是可以在任何位置加

class Solution {
public:
    string shortestPalindrome(string s) {
        if (s.empty()) return "";
        string t = s;
        reverse(t.begin(), t.end());
        int n = s.length();
        vector<vector<int>> f(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s[i - 1] == t[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = max(f[i][j - 1], f[i - 1][j]);
                }
            }
        }
        string res;
        for (int i = n, j = n; i > 0 || j > 0;) {
            if (i == 0) {
                res += t[j - 1];
                --j;
            } else if (j == 0) {
                res += s[i - 1];
                --i;
            } else if (s[i - 1] == t[j - 1]) {
                res += s[i - 1];
                --i;
                --j;
            } else {
                if (f[i][j] == f[i][j - 1]) {
                    res += t[j - 1];
                    --j;
                } else {
                    res += s[i - 1];
                    --i;
                }
            }
        }
        return res;
    }
};