AC JAVA solution Manacher’s algorithm


  • 0
    W

    Please see http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html for explanation.

    public class Solution {
        public String longestPalindrome(String s) {
            if (s == null || s.length() <= 1) return s;
            s = process(s);
            int[] P = new int[s.length()];
            int mid = 0;
            int max = 0;
            for (int i = 1; i < s.length() - 1; i++) {
                P[i] = i < max ? Math.min(P[mid - (i - mid)], max - i) : 0;
                while (s.charAt(i - P[i] - 1) == s.charAt(i + P[i] + 1)) P[i]++;
                if (i + P[i] > max) {
                    mid = i;
                    max = P[i];
                }
            }
            int maxLen = 0;
            mid = 0;
            for (int i = 0; i < s.length(); i++) {
                if (P[i] > maxLen) {
                    mid = i;
                    maxLen = P[i];
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = mid - maxLen; i <= mid + maxLen; i++) {
                if (s.charAt(i) != '#') sb.append(s.charAt(i));
            }
            return sb.toString();
        }
        private String process(String s) {
            StringBuilder sb = new StringBuilder();
            sb.append('^');
            for (int i = 0; i < s.length(); i++) {
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
            return sb.toString();
        }
    }

Log in to reply
 

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