fork download
copy 
  1. public class Manacher {
  2.     private int[]  p;  // p[i] = length of longest palindromic substring of t, centered at i
  3.     private String s;  // original string
  4.     private char[] t;  // transformed string
  5.  
  6.     public Manacher(String s) {
  7.         this.s = s;
  8.         preprocess();
  9.         p = new int[t.length];
  10.  
  11.         int center = 0, right = 0;
  12.         for (int i = 1; i < t.length-1; i++) {
  13.             int mirror = 2*center - i;
  14.  
  15.             if (right > i)
  16.                 p[i] = Math.min(right - i, p[mirror]);
  17.  
  18.             // attempt to expand palindrome centered at i
  19.             while (t[i + (1 + p[i])] == t[i - (1 + p[i])])
  20.                 p[i]++;
  21.  
  22.             // if palindrome centered at i expands past right,
  23.             // adjust center based on expanded palindrome.
  24.             if (i + p[i] > right) {
  25.                 center = i;
  26.                 right = i + p[i];
  27.             }
  28.         }
  29.  
  30.     }
  31.  
  32.     // Transform s into t.
  33.     // For example, if s = "abba", then t = "$#a#b#b#a#@"
  34.     // the # are interleaved to avoid even/odd-length palindromes uniformly
  35.     // $ and @ are prepended and appended to each end to avoid bounds checking
  36.     private void preprocess() {
  37.         t = new char[s.length()*2 + 3];
  38.         t[0] = '$';
  39.         t[s.length()*2 + 2] = '@';
  40.         for (int i = 0; i < s.length(); i++) {
  41.             t[2*i + 1] = '#';
  42.             t[2*i + 2] = s.charAt(i);
  43.         }
  44.         t[s.length()*2 + 1] = '#';
  45.     }
  46.  
  47.     // longest palindromic substring
  48.     public String longestPalindromicSubstring() {
  49.         int length = 0;   // length of longest palindromic substring
  50.         int center = 0;   // center of longest palindromic substring
  51.         for (int i = 1; i < p.length-1; i++) {
  52.             if (p[i] > length) {
  53.                 length = p[i];
  54.                 center = i;
  55.             }
  56.         }
  57.         return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
  58.     }
  59.  
  60.     // longest palindromic substring centered at index i/2
  61.     public String longestPalindromicSubstring(int i) {
  62.         int length = p[i + 2];
  63.         int center = i + 2;
  64.         return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
  65.     }
  66.  
  67.  
  68.  
  69.     // test client
  70.     public static void main(String[] args) {
  71.         String s = args[0];
  72.         Manacher manacher = new Manacher(s);
  73.         StdOut.println(manacher.longestPalindromicSubstring());
  74.         for (int i = 0; i < 2*s.length(); i++)
  75.             StdOut.println(i +  ": " + manacher.longestPalindromicSubstring(i));
  76.  
  77.     }
  78. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class Manacher is public, should be declared in a file named Manacher.java
public class Manacher {
       ^
Main.java:73: error: cannot find symbol
        StdOut.println(manacher.longestPalindromicSubstring());
        ^
  symbol:   variable StdOut
  location: class Manacher
Main.java:75: error: cannot find symbol
            StdOut.println(i +  ": " + manacher.longestPalindromicSubstring(i));
            ^
  symbol:   variable StdOut
  location: class Manacher
3 errors
stdout
copy 
Standard output is empty
https://ideone.com/XnVIwU
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!