001package algs53; // section 5.3 002import stdlib.*; 003/* ************************************************************* 004 * Compilation: javac Manacher.java 005 * Execution: java Manacher text 006 * 007 * Computes the longest palindromic substring in linear time 008 * using Manacher's algorithm. 009 * 010 * Credits: The code is lifted from the following excellent reference 011 * http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html 012 * 013 ***************************************************************/ 014 015public class XManacher { 016 private final int[] p; // p[i] = length of longest palindromic substring of t, centered at i 017 private final String s; // original string 018 private final char[] t; // transformed string 019 020 public XManacher(String s) { 021 this.s = s; 022 t = preprocess(s); 023 p = new int[t.length]; 024 025 int center = 0, right = 0; 026 for (int i = 1; i < t.length-1; i++) { 027 int mirror = 2*center - i; 028 029 if (right > i) p[i] = Math.min(right - i, p[mirror]); 030 031 // attempt to expand palindrome centered at i 032 while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) 033 p[i]++; 034 035 // if palindrome centered at i expands past right, 036 // adjust center based on expanded palindrome. 037 if (i + p[i] > right) { 038 center = i; 039 right = i + p[i]; 040 } 041 } 042 043 } 044 045 // Transform s into t. 046 // For example, if s = "abba", then t = "$#a#b#b#a#@" 047 // the # are interleaved to avoid even/odd-length palindromes uniformly 048 // $ and @ are prepended and appended to each end to avoid bounds checking 049 public char[] preprocess(String s) { 050 char[] t = new char[s.length()*2 + 3]; 051 t[0] = '$'; 052 t[s.length()*2 + 2] = '@'; 053 for (int i = 0; i < s.length(); i++) { 054 t[2*i + 1] = '#'; 055 t[2*i + 2] = s.charAt(i); 056 } 057 t[s.length()*2 + 1] = '#'; 058 return t; 059 } 060 061 // longest palindromic substring 062 public String longestPalindromicSubstring() { 063 int length = 0; // length of longest palindromic substring 064 int center = 0; // center of longest palindromic substring 065 for (int i = 1; i < p.length-1; i++) { 066 if (p[i] > length) { 067 length = p[i]; 068 center = i; 069 } 070 } 071 return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2); 072 } 073 074 // longest palindromic substring centered at index i/2 075 public String longestPalindromicSubstring(int i) { 076 i = i + 2; 077 int length = p[i]; 078 int center = i; 079 return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2); 080 } 081 082 083 084 // test client 085 public static void main(String[] args) { 086 String s = args[0]; 087 XManacher manacher = new XManacher(s); 088 StdOut.println(manacher.longestPalindromicSubstring()); 089 for (int i = 0; i < 2*s.length(); i++) 090 StdOut.println(i + ": " + manacher.longestPalindromicSubstring(i)); 091 092 } 093}