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. }

advertisement
Manacher Algorithm Test
 
 
Enter String
civicradarrevivermalayalammadamnoon
 
Longest Palindrome : malayalam

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn