6ms Solution using Manacher's Algorithm, Linear Time O(n), C++


  • 0
    M

    Please wiki Mandacher's algorithm for detailed explanation.

    class Solution {
    public:
    string longestPalindrome(string s) {
        if (s.empty()) return s;
        if (s.size()==1) return s;
        if (s.size()==2) return (s[0]==s[1])? s:s.substr(0, 1);
        
        
        
        // dynamic programming
        vector<int> dp(s.size()*2+1, 0); // contains longest palindrome length
        dp[1] = 1;
        int j, k; // j: mirror to the center, k: span of current palindrome
        int center = 1, end = 2; 
    
        for(int i=2;i<dp.size();i++){
            if (i<end) {
                j = center-(i-center); // j = i's mirror to the center
                if (dp[j]+i<end) dp[i] = dp[j]; // case 1, 
                else { // case 2
                    k = end-i;
                    while((i+k)<dp.size() && (i-k)>=0 && !((i+k)%2==1 && (s[(i+k)/2] != s[(i-k)/2]))) dp[i] = k++;
                    end = i+dp[i], center = i; // update new end and new center
                }
            } else { // case 3
                k=0;
                while((i+k)<dp.size() && (i-k) >= 0 && !((i+k)%2==1 && (s[(i+k)/2] != s[(i-k)/2]))) dp[i] = k++;
                end = i+dp[i], center = i; // update new end and new center
            }
        }
        
        auto maxIter = max_element(dp.begin(), dp.end());
        int maxlength = *maxIter;
        int maxind = distance(dp.begin(), maxIter);
        return s.substr((maxind-maxlength)/2, maxlength);
        
    }
    };

Log in to reply
 

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