214. Shortest Palindrome

problem description

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

algorithm thought

这里我开始直接用暴力匹配的方法解决，发送时间和空间复杂度被拉满了。过不了最后一个测试样例。后来看discuss，发现可以使用KMP算法解这题。

还是那句话，碰到字符串问题，要不就是动态规划，还不就是匹配（KMP，Trie），再就是少数的回溯。

做这题之前，我一直没有真正理解KMP。只是会用KMP，知道他是一种匹配算法。KMP中匹配字符串最后的index表明的是匹配字符串最前面一段和被匹配字符串最后一段的匹配情况。用在这里，恰恰合适。将字符串翻转之后，匹配出相同的前后缀，最后再将前缀加到原来字符串前面即可

code

class Solution {
public:
    string shortestPalindrome(string s) {
        if(s.size()==0)
            return s;
        vector<int> next(s.size(),-1);
        string rs(s);
        reverse(s.begin(),s.end());
        getnext(next,rs);
        int j=0,i=0;
        while(i<s.size()){
            if(j==-1||rs[j]==s[i]){
                i++;j++;
            }else{
                j=next[j];
            }
        }
        s+=rs.substr(j);
        return s;
    }
    void getnext(vector<int>&next,string&s){
        int j=-1,i=0;
        while(i<s.size()-1){
            if(j==-1||s[j]==s[i]){
                i++;j++;
                next[i]=j;
            }else{
                j=next[j];
            }
        }
    }
};

algorithm analysis

KMP只需要两次遍历字符串，时间复杂度O(n)