题目

shortest-palindrome

算法

* kmp

代码

* kmp

http://www.cnblogs.com/ganganloveu/p/4621327.html

class Solution {
public:
    string shortestPalindrome(string s) {
        if(s == "")
            return s;
        string s2 = s;
        reverse(s2.begin(), s2.end());
        string news = s + s2;
        int n = news.size();
        vector<int> next(n+1);
        buildNext(news, next, n);
        if(next[n] > s.size())
            next[n] = next[n] + 1 - s.size();
        string pres = s.substr(next[n]);
        reverse(pres.begin(), pres.end());
        return pres + s;
    }
    void buildNext(string& s, vector<int>& next, int n)
    {
        int k = -1;
        int j = 0;
        next[0] = -1;
        while(j < n)
        {
            if(k == -1 || s[j] == s[k])
            {
                k ++;
                j ++;
                next[j] = k;
            }
            else
            {
                k = next[k];
            }
        }
    }
};

* 简化版本kmp

class Solution {
public:
    string shortestPalindrome(string s) {
        string r = s;
        reverse(r.begin(), r.end());
        string t = s + "#" + r;
        vector<int> p(t.size(), 0);
        for (int i = 1; i < t.size(); ++i) {
            int j = p[i - 1];
            while (j > 0 && t[i] != t[j]) j = p[j - 1];
            p[i] = (j += t[i] == t[j]);
        }
        return r.substr(0, s.size() - p[t.size() - 1]) + s;
    }
};