``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 ``` ```package algs53; // section 5.3 import stdlib.*; /* ************************************************************* * Compilation: javac Manacher.java * Execution: java Manacher text * * Computes the longest palindromic substring in linear time * using Manacher's algorithm. * * Credits: The code is lifted from the following excellent reference * http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html * ***************************************************************/ public class XManacher { private final int[] p; // p[i] = length of longest palindromic substring of t, centered at i private final String s; // original string private final char[] t; // transformed string public XManacher(String s) { this.s = s; t = preprocess(s); p = new int[t.length]; int center = 0, right = 0; for (int i = 1; i < t.length-1; i++) { int mirror = 2*center - i; if (right > i) p[i] = Math.min(right - i, p[mirror]); // attempt to expand palindrome centered at i while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) p[i]++; // if palindrome centered at i expands past right, // adjust center based on expanded palindrome. if (i + p[i] > right) { center = i; right = i + p[i]; } } } // Transform s into t. // For example, if s = "abba", then t = "\$#a#b#b#a#@" // the # are interleaved to avoid even/odd-length palindromes uniformly // \$ and @ are prepended and appended to each end to avoid bounds checking public char[] preprocess(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] = '#'; return t; } // longest palindromic substring public String longestPalindromicSubstring() { int length = 0; // length of longest palindromic substring int 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; } } return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2); } // longest palindromic substring centered at index i/2 public String longestPalindromicSubstring(int i) { i = i + 2; int length = p[i]; int center = i; return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2); } // test client public static void main(String[] args) { String s = args[0]; XManacher manacher = new XManacher(s); StdOut.println(manacher.longestPalindromicSubstring()); for (int i = 0; i < 2*s.length(); i++) StdOut.println(i + ": " + manacher.longestPalindromicSubstring(i)); } } ```