Java solution in Manacher algorithm


  • 0
    Y
        public String longestPalindrome(String s) {
            // Manacher algorithm
            String t = "#";
            for(int i = 0; i < s.length(); i++) {
                t += s.substring(i, i+1) + "#";
            }
            int mx = 0, d = 0;
            int max_start = -1, max_p = 0;
            int[] p = new int[t.length()];
            Arrays.fill(p, 0);
            for(int i = 1; i < t.length(); i++) {
                p[i] = (mx >= i && 2*d >= i) ? Integer.min(p[2 * d - i], mx - i) : 1;
                while(p[i] + i < t.length() && i - p[i] >= 0 && t.charAt(p[i] + i) == t.charAt(i - p[i])) {
                    p[i]++;
                }
                if(p[i] + i > mx) {
                    mx = p[i] + i;
                    d = i;
                }
                if(p[i]-1 > max_p){
                    max_p = p[i] - 1;
                    max_start = (i-p[i]+1)/2;
                }
            }
            if(max_start >= 0) return s.substring(max_start, max_start+max_p);
            else return "";
     
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.