Notes of Manacher Algorithm


#1

I spend a few days to understand the Manacher’s algorithm. It’s really smart algorithm.
I share my notes to understand this algorithm. I hope some’s help.

Here is my notes:

And this is my code:

public class Solution{
    static boolean isDebug = false;

    public String longestPalindrome(String A) {
        int n = A.length();
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
           builder.append("#").append(A.charAt(i));
        }
        builder.append("#");
        A = builder.toString();
        n = builder.length();

        int j, maxJ = 0;
        int[] R = new int[n];
        String result = "";

        for (int i = 0; i < n; i++) {
            // (1) Is there palindrome?
            j = R[i];
            while((i - j >= 0) && (i + j < n) &&
                   A.charAt(i - j) == A.charAt(i + j)) j++;
            if (j == R[i]) {
                continue;
            }

            R[i] = j;

            // (2) If palindrome, copy the information
            int k = 1;
            while((i - k >= 0) && (k + R[i - k] < j)) {
                R[i + k] = R[i - k];
                k++;
            }

            // (3) Keep the longest palindrome
            if (j > maxJ) {
                maxJ = j;
                j--;
                result = A.substring(i - j, i + j + 1);
            }
        }

        if (isDebug) {
            System.out.println(Arrays.toString(R));
        }

        return result.replaceAll("#", "");
    }
}

#2

One of the most beautiful explanations of manacher algorithm, thank you so much brother.


#3

it took me 2 hours to understand the whole concept but it was worth it thank you for this