22-line C++ Manacher’s Algorithm O(n) Solution


  • 22
    L

    This implements the Manacher's Algorithm, which is illustrated here: http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html. Although there are nested loops, there is shortcut in computation, so it is still O(n).

    class Solution {
    public:
        string longestPalindrome(string s) 
        {
            string T;// Transform S to T
            for(int i=0;i<s.size();i++)
                T+="#"+s.substr(i,1);
            T.push_back('#');
    
            vector<int> P(T.size(),0); // Array to record longest palindrome
            int center=0,boundary=0,maxLen=0,resCenter=0;
            for(int i=1;i<T.size()-1;i++) {
                int iMirror=2*center-i; // calc mirror i = center-(i-center)
                P[i]=(boundary>i)?min(boundary-i,P[iMirror]):0; // shortcut
                while(i-1-P[i]>=0&&i+1+P[i]<=T.size()-1&&T[i+1+P[i]] == T[i-1-P[i]]) // Attempt to expand palindrome centered at i
                    P[i]++;
                if(i+P[i]>boundary) { // update center and boundary
                    center = i;
                    boundary = i+P[i];
                }
                if(P[i]>maxLen) { // update result
                    maxLen = P[i];
                    resCenter = i;
                }    
            }
            return s.substr((resCenter - maxLen)/2, maxLen);
        }
    };

  • 2
    Z

    If the string s has the char '#',you solution will fail.For example,the string s is "##".


  • 0
    B

    @zywscq those boundaries introduced in the string are logical only, helpful in understanding how the algo works but can be omitted in the actual implementation. Instead, indices are manipulated in certain way as to account for presence of logical boundaries: basically can check for oddness of current expansion indices and then either make the comparison of (actual) characters or just increase span (because boundaries are always matching). This removes restriction for string to not contain some special characters


Log in to reply
 

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