Manacher's Algorithm using C++ (8ms)


  • 0
    B
    class Solution {
    public:
    int manacher(string& str){
        int n = str.length();
        vector<int> p(n+1);
        
        int center = 0;
        for(int i = 1; i <= n; i ++){
            if(i <= center + p[center]){
                int j = 2 * center - i;
                if(i + p[j] < center + p[center]){
                    p[i] = p[j];
                }else{
                    int k = center + p[center] + 1;
                    j = 2 * i - k;
                    
                    while(j >= 1 && k <= n && str[k-1] == str[j-1]){
                        k ++;
                        j --;
                    }
                    center = i;
                    p[i] = k - i - 1;
                }
            }else{
                int k = i + 1;
                int j = i - 1;
                while(j >= 1 && k <= n && str[j-1] == str[k-1]){
                    k ++;
                    j --;
                }
                center = i;
                p[i] = k - i - 1;
            }
        }
        
        int ret = -1;
        for(int i = 1; i <= n; i ++){
            if(i - p[i] == 1) ret = max(ret, p[i]);
        }
        return ret;
    }
    string shortestPalindrome(string s) {
        string str = "#";
        int len = s.length();
        for(int i = 0; i < len; i ++){
            str += s[i];
            str += "#";
        }
        
        int lsp = manacher(str);
        string tmp = s.substr(lsp);
        reverse(tmp.begin(), tmp.end());
        return tmp + s;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.