Manacher's algorithm: longest palindromic substring problem

In this post I'll try to explain Manacher's algorithm in a simple way. Manacher's algorithm is a solution for finding the longest palindromic substring of a given string.

A palindrome is a sequence of symbols or elements that reads the same forward or reversed.
Examples of a few palindromes:

radar    level    rotor    noon

abba    aba    b    xxx1y1xxx

Manacher's algorithm is a really good/fast solution for this problem since its time and space complexity is O(N).

Pre-process string S

The first step of the algorithm is to pre-process a given string S, into string T, by inserting a special character between every character of S and also at both ends. For the algorithm future convenience, a distinct special character should then be placed at both ends. This pre-processing is done just to handle both even and odd sized S strings gracefully.

If say, '#' is used as the main special character, these are some examples of the original strings and their resulting transformations:

S: abba     T: ^#a#b#b#a#$

S: a        T: ^#a#$

Now would be a good time to code this first step. Try to code it for yourself before seeing the snippet below, it should be pretty straight forward.
When you are done, compare your solution with the pseudo code below.

preprocessManacherAlgorithm(s) {
    if (s.length() == 0)
        return "^$";

    t = "^";
    for (i = 0; i < s.length(); i++)
        t += "#" + s[i];
    t += "#$";

    return t;
}

Process string T

After having pre-processed a given string S into string T, the next step is to process string T itself. To do that, an auxiliary array P with size equal to the length of T is required.

The content of the i-th element of P corresponds to the size of the maximum expansion to both sides of the i-th element of T in order to form a palindrome.

Was that too confusing? Look at the example below to better comprehend the purpose of P.



What is the longest palindromic substring contained in T? The answer is # a # b # a #, which has a length of 7 characters, right? Also notice that the character 'b', i = 4, is the center of the palindrome.

So, now the question is: how many characters of the palindrome are to the right or to the left of the palindrome's center? Or in other words: what is the size of the expansion to both left or right of the center character which makes up the palindrome?
The answer is 3. The image below illustrates this.



The goal is to populate P, and that task should now be easy.
The result is as follows:



Important note:
It is a good idea to have an auxiliary variable maxPalCenterID with the index of the highest value in P and update it while we populate P.

After having populated P, the longest palindromic substring is very easy to fetch from the original string S.

Since there is a special character at the start of T due to the pre-processing, and also another special character between every character of S, the palindrome start index is given by the formula below.

palStartID = (maxPalCenterID - 1 - P[maxPalCenterID]) / 2;

At this time, the longest palindromic substring has been found successfully, and though this is already a pretty good solution, it does not have a time and space complexity of O(N). In order to reach that complexity, there is a trick which Manacher's algorithm makes use of.

You should try to code by yourself the algorithm so far. Do not peek the snippet below. It is important that you try for yourself and only after compare your solution with the pseudo code below.

almostManacherAlgorithm(s) {
    t = preprocessManacherAlgorithm(s);

    n = t.size();
    P[n, 0]; // array of size n filled with 0

    maxPalCenterID = 1;
    for (i = 1; i < n - 1; i++) {
        while (t[i + 1 + P[i]] == t[i - 1 - P[i]])
            P[i]++;

        if (P[i] > P[maxPalCenterID])
            maxPalCenterID = i;
    }

    maxPalSize = P[maxPalCenterID];
    palStartID = (maxPalCenterID - 1 - maxPalSize) / 2;

    return s.substr(palStartID, maxPalSize);
}

Make it O(N)

Now that we have a functional algorithm, can it run faster? If yes, what can be done to make it run faster?

The trick resides in the symmetrical property of palindromes. Consider the following example, where C is the center of a palindrome and L and R are the left and right bounds, respectively.



Now populate P until R, the right bound of the palindrome with center in C.

Notice the symmetry? If there was a mirror at C, the content of P between L and R would be completely symmetric, just like it actually is! Check it for yourself below.



And now you might be thinking: we can save a lot of computations just by copying the half of a palindrome to the left of the center, mirror it, and pasting to the right! And then keep populating P after R with the same principle!

Go ahead and try that for yourself. Populate P based on this concept for C = 8. You should get something like this, which is wrong if you look carefully:



The right answer would be:



Well, that is still a great conclusion! Although it is not completely correct, you are very close to finding the trick!

As you may already be thinking, this concept works, but it fails at certain point. What is the limit?

If you examine a couple of more examples, this limit will be very easy to detect:
When P[i'] is less or equal to R-i, then P[i] is always equal to the minimum of these values: R-i or P[i']; Otherwise, the only valid information we have is that P[i'] is greater or equal to P[i], which is already a very valuable information! If this is the case, we just have to try and expand this palindrome to find P[i].

The final part that completes the trick is answered by the following question: when should C be updated? Again, if a few examples are examined by hand, it is not hard to find that:

Whenever a palindrome centered at i expands past the right bound of the palindrome centered at C (in other words, if it expands past R), C is assigned the value of i and R is updated according to the content of P[i] and i itself. Does that make sense? I really hope so! :)

And that is it! This concludes the beautiful Manacher's algorithm: a tool for finding the longest palindromic substring in O(N).

Now you just have to add these little extras to the previous code. Do not peek the snippet below. Once again, it is important that you try for yourself. Then you may compare your solution with the pseudo code below.

manacherAlgorithm(s) {
    t = preprocessManacherAlgorithm(s);

    n = t.size();
    P[n, 0]; // array of size n filled with 0
    C = R = 0;

    maxPalCenterID = 1;
    for (i = 1; i < n - 1; i++) {
        // i' = C - (i-C)
        ii = 2 * C - i;

        // save several computations
        P[i] = (R > i) ? min(R - i, P[ii]) : 0;

        // expand palindrome
        while (t[i + 1 + P[i]] == t[i - 1 - P[i]])
            P[i]++;

        // update index of the center of the biggest palindrome
        if (P[i] > P[maxPalCenterID])
            maxPalCenterID = i;

        // adjust center if palindrome
        // centered at i expands past R
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
    }

    maxPalSize = P[maxPalCenterID];
    palStartID = (maxPalCenterID - 1 - maxPalSize) / 2;

    return s.substr(palStartID, maxPalSize);
}

You might be interested in checking this tutorial if you did not understand my explanation. I learnt this algorithm from there.

Maze Generation Algorithm

Recently, I had to develop a game that required a random maze to be generated. The logic behind it is not that hard, but some people may have trouble trying to code it, so I decided I would blog about it.

This post is a how-to generate random labyrinths. Keep in mind there are a lot of algorithms and this is not the best neither the most optimized. In my opinion it is the simplest though.

Introduction

What you will need:

• lab: an array to store the labyrinth (I'll be using a 2D array);
• visitedCells: a secondary array to keep record of the visited cells;
• guideCell: the coordinates of the head of the path;
• pathHistory: a stack to keep a record of the path taken.

How the algorithm works:

• The guide cell starts next to the exit;
• The guide cell advances to a random unvisited cell;
• The guide cell keeps advancing until there are no unvisited cells around it;
• When there are no unvisited cells around, the stack gets useful:
• back trace to a point of the path where there is at least one unvisited cell and develop the algorithm from there;
• The maze is completely finished when all cells have been visited.
• An even easier way to know it is finished is when the stack gets empty.

Restrictions:

• The dimension of the maze needs to be an odd number.

Detailed Algorithm Analysis

Let's say we need to generate a 7x7 maze.

The first step is to fill the 2D array with walls (I'll be using 'X' to display walls). After this we need to free the cells which have odd x and y coordinates, just like the picture below:

And this is the base matrix where the algorithm will work. That's why the the maze needs to have an odd dimension.
The next step would be randomly picking one free cell (as long as it is right next to the maze borders) and marking it as the guideCell. After that, place an 'S' on the maze border to mark the exit:

S: exit

+: guideCell

The next step is to create the visitedCells array to keep track of the cells which have been visited or not. This array will not be 7x7 but 3x3. The dimension of the visitedCells array is given by

visitedCellsDimension = (labDimension - 1) / 2

Here is the current state of the visitedCells array:

.: unvisited cell

+: visited cell

Ok, by this time we have our lab array and our visitedCell ready. We just need to push the guideCell coords to the stack:

Now that we have everything ready, let the algorithm start working! Yay! :D

First we need to generate a random direction and check if that cell has already been visited. If not, the guide cell will advance to that direction.

Assume that the computer randomly says: "guideCell, go down!". The cell below the guideCell current location has not yet been visited according to the visitedCells array, so this is what will happen:

• the guideCell coords will be updated and pushed to the stack;
• the visitedCells matrix will be updated:
• a '+' will be marked at {2, 1};
• the lab array will also be updated:
• the 'X' on {5, 2} will be removed.

This is how the containers look at this point:

Ok let's speed up things a little bit. I hope you are catching up with me.

Let's say the computer generated this directions randomly:

• right;
• up;
• left;
• down;
• right.

The 1st direction (right) will be ignored because the guide cell can not go right! That's the border of the maze!
The 2nd direction generated (up) will also be ignored because according to the visitedCells, the cell above the guideCell has already been visited. Do you get it? :)
The 3rd direction is a valid one though! The guideCell can indeed go left. So this is what will happen:

The 4th direction generated was 'down':

And finally, the 5th direction generated was 'right':

Ok, by now you should have realized how the algorithm works.

Notice what happens now:

• If the computer generates right or down, the guideCell can not go there because that is the maze borders!
• If the computer generates left or up, the guideCell can not go there as well because according to the visitedCells array, both cells in that direction have already been visited!

It is a dead end! So, how do we finish generating the maze? It's not finished yet...

Well, it's not that hard! This is why we have the stack with the history of the path we took!
When we run into this problem we just need to back trace the stack and look for a cell that has at least one neighbor that has not yet been visited. When we do find this cell, it becomes our new guideCell.

Let me use the example we have been working on to illustrate what I mean:
The current guideCell has no unvisited cells as neighbors, so we need to remove it from the stack. And since we removed it, the top of the stack is {1, 2}, and this cell has at least one neighbor unvisited: This is our new guideCell.

And since there is only one valid direction (left), the following algorithm iterations will be:

And at this point, once again, we got to a dead end. What did we do when this happened before? That is right! We popped the stack until we found a cell that had at least one unvisited neighbor.

This time though, we will pop the stack and won't find a cell that matches this condition. Why? Because all cells have been visited! You can check that by looking to the visitedCells array.
The program will therefore be popping the stack and eventually empty it.

And that concludes the algorithm: when the stack gets empty, all the cells have been visited and the maze generation was successfully completed! :)

Here is an example of a 31x31 maze generated with this algorithm:

I hope this helped you and was not too confusing... Cheers!