Why the Manacher Solution is slower than simple O(n^2) solution?


  • 1
    K

    Below is my code using Manacher's method, costs 20ms, and I've seen some others Manacher solutions cost 12ms. Manacher's method only cosumes O(n) time, so why simple O(n^2) solution only costs 4ms?

    class Solution { 
    public:
    string longestPalindrome(string s) {
        string ss;
        int p[2003];
        int mx=0,center=0,pmax=1,imax=0;
        if(s.empty()) return s;
        for(int i=0;i<s.size();i++)
            ss=ss+'#'+s[i];
        ss.push_back('#');
        for(int i=0;i<ss.size();i++){
            if(mx<=i){
                p[i]=1;
            }
            else{
               p[i]=min(mx-i,p[2*center-i]); 
            }
            while(i-p[i]>=0&&i+p[i]<ss.size()&&ss[i-p[i]]==ss[i+p[i]]){
                p[i]++;
            }
            if(i+p[i]>mx){
                mx=i+p[i];
                center=i;
            }
            if(p[i]>pmax){
                pmax=p[i];
                imax=i;
            }
        }
        int j;
    
        j=imax-pmax+2;
        return s.substr(j/2,pmax-1);
    }
    

    };


Log in to reply
 

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