Java Program to Implement Manacher Algorithm

«
»
This is a Java Program to Implement Manacher Algorithm. Manacher algorithm is used to find largest palindromic substring in a given string efficiently.

Here is the source code of the Java Program to Implement Manacher Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to implement Manacher Algorithm
  3.  **/
  4.  
  5. import java.io.BufferedReader;
  6. import java.io.InputStreamReader;
  7. import java.io.IOException;
  8.  
  9. /** Class Manacher **/
  10. public class Manacher
  11. {
  12.     /** function to preprocess string **/
  13.     public String preProcess(String str)
  14.     {
  15.         int len = str.length();
  16.         if (len == 0) 
  17.             return "^$";
  18.         String s = "^";
  19.         for (int i = 0; i < len; i++)
  20.             s += "#" + str.charAt(i);         
  21.         s += "#$";
  22.         return s;
  23.     }
  24.     /** function to get largest palindromic substring **/
  25.     public String getLongestPalindrome(String str)
  26.     {
  27.         /** preprocess string **/
  28.         char[] s = preProcess(str).toCharArray();
  29.         int N = s.length;
  30.         int[] p = new int[N + 1];
  31.         int id = 0, mx = 0;
  32.         for (int i = 1; i < N - 1; i++) 
  33.         {
  34.              p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 0;
  35.              while (s[i + 1 + p[i]] == s[i - 1 - p[i]]) 
  36.                  p[i]++;
  37.              if (i + p[i] > mx) 
  38.              {
  39.                  mx = i + p[i];
  40.                  id = i;
  41.              }
  42.         }
  43.         /** length of largest palindrome **/
  44.         int maxLen = 0;
  45.         /** position of center of largest palindrome **/
  46.         int centerIndex = 0;
  47.         for (int i = 1; i < N - 1; i++) 
  48.         {
  49.             if (p[i] > maxLen) 
  50.             {
  51.                 maxLen = p[i];
  52.                 centerIndex = i;
  53.             }
  54.         }
  55.         /** starting index of palindrome **/
  56.         int pos = (centerIndex - 1 - maxLen)/2;
  57.         return str.substring(pos , pos + maxLen);        
  58.     }
  59.     /** Main Function **/
  60.     public static void main(String[] args) throws IOException
  61.     {    
  62.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  63.         System.out.println("Manacher Algorithm Test\n");
  64.         System.out.println("\nEnter String");
  65.         String text = br.readLine();
  66.  
  67.         Manacher m = new Manacher(); 
  68.         String longestPalindrome = m.getLongestPalindrome(text); 
  69.         System.out.println("\nLongest Palindrome : "+ longestPalindrome);    
  70.     }    
  71. }

Manacher Algorithm Test
 
 
Enter String
civicradarrevivermalayalammadamnoon
 
Longest Palindrome : malayalam

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.