Manacher's Algorithm

For string S, find the longest palindromic substring.
Example: S = "bananas" LPS = "anana"


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.virendra.questions;

public class Manacher {

    public Manacher(String s) {
        
        char[] T = new char[s.length()*2 + 3];
        T[0] = '$';
        T[s.length()*2 + 2] = '@';
        for (int i = 0; i < s.length(); i++) {
            T[2*i + 1] = '#';
            T[2*i + 2] = s.charAt(i);
        }
        T[s.length()*2 + 1] = '#';
        
        
        int[]  P = new int[T.length];
        int center = 0, right = 0;
        
        for (int i = 1; i < T.length-1; i++) {
            int mirr = 2*center - i;

            if (i < right)
                P[i] = Math.min(right - i, P[mirr]);
            
          while (T[i + (1 + P[i])] == T[i - (1 + P[i])])
                P[i]++;

            if (i + P[i] > right) {
                center = i;
                right = i + P[i];
            }
        }
        
        int length = 0;   // length of longest palindromic substring
        center = 0;   // center of longest palindromic substring
        for (int i = 1; i < P.length-1; i++) {
            if (P[i] > length) {
                length = P[i];
                center = i;
            }
        }
        System.out.println(s.substring((center - 1 - length) / 2, (center - 1 + length) / 2));

    }
	
    public static void main(String[] args) {
        String s = "abababa";
        Manacher manacher = new Manacher(s);
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa

    Ninja Programmer