Easy C++ Manacher


  • 4

    The idea is to find the longest palindromic substring of s that begins with s[0]. Then take the remaining susbtring, reverse it and append it to the beginning of s.

    For example, given s = "aacecaaa", the longest palindromic substring beginning with s[0] = 'a' is "aacecaa" and the remaining substring is "a". Reverse it and append it to the beginning of s gives "aaacecaaa".

    For s = "abcd", the longest palindromic substring beginning with s[0] = 'a' is "a" and the remaining substring is "bcd". Reverse it and append it to the beginning of s gives "dcbabcd".

    The most difficult part is to implement the Manacher's algorithm to find the longest palindromic substring starting with s[0]. Please refer to this nice article if you want to know how it works.

    The code is as follows.

    class Solution {
    public:
        string shortestPalindrome(string s) {
            string t = process(s);
            int n = t.length(), center = 0, right = 0;
            int* palin = new int[n];
            for (int i = 1; i < n - 1; i++) {
                int i_mirror = 2 * center - i;
                palin[i] = (right > i) ? min(palin[i_mirror], right - i) : 0;
                while (t[i + palin[i] + 1] == t[i - palin[i] - 1])
                    palin[i]++;
                if (i + palin[i] > right) {
                    center = i;
                    right = i + palin[i];
                }
            }
            int pos;
            for (int i = n - 2; i; i--) {
                if (i - palin[i] == 1) {
                    pos = palin[i];
                    break;
                }
            }
            string tail = s.substr(pos); 
            reverse(tail.begin(), tail.end());
            return tail + s;
        }
    private:
        string process(string& s) {
            int n = s.length();
            string t(2 * n + 3, '#');
            t[0] = '$'; t[2 * n + 2] = '%';
            for (int i = 0; i < n; i++)
                t[2 * (i + 1)] = s[i];
            return t;
        }
    };
    

    Note that this part of the code is just to find the ending position of the longest palindromic substring begining with s[0].

    int pos;
    for (int i = n - 2; i; i--) {
        if (i - palin[i] == 1) {
            pos = palin[i];
            break;
        } 
    } 
    

  • 0
    X

    thanks, it helps me a lot


  • 0
    S

    Hi, could you please explain more about "find the ending position " part ? How did you come up it? Thanks :-)


  • 0

    Hi, that part has no mystery, but just a point of the Manacher's algorithm. This algorithm is not easy to explain and I would like to recommend you to this nice article.


Log in to reply
 

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