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}