C++ solution based on Manacher's algorithm O(n)


  • 0
    B
    string shortestPalindrome(string s) {
        string ss(s.length()*2+3, 'c'); // avoid ss+=, which will cause MLE
        ss[0]='$'; ss[1]='#';
        for(int i=0; i<s.length(); ++i){
            ss[2*(i+1)]=s[i];ss[2*(i+1)+1]='#';
        }
        ss[2*s.length()+2]='%';
        cout<<ss<<endl;
        int id=0, mx=1;
        vector<int> p(ss.length()+5, 0);
        for(int i=1; i+1<ss.length(); ++i){
            p[i]=mx>i?min(p[2*id-i], mx-i):1;
            while(ss[i+p[i]]==ss[i-p[i]]) p[i]++;
            if(i+p[i]>mx){
                id=i;
                mx=i+p[i];
            }
        }
        int k=-1;
        for(int i=1; i+1<ss.length(); ++i){
            if(p[i]==i)
                k=i;
        }
        ss.clear();
        string ans;
        int av=p[k]-1;
        ans=s.substr(av);
        reverse(ans.begin(), ans.end());
        cout<<av<<" "<<ans<<endl;
        
        return ans+s.substr(0, av)+s.substr(av);
    }

Log in to reply
 

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