O(N) Manacher Algorithm implemented with Java


  • 1
    R
        public String longestPalindrome(String s) {
            char[] str = preProcess(s).toCharArray();
            int N = str.length;
            int[] p = new int[N + 1];
            int id = 0, mx = 0;
            for (int i = 1; i < N - 1; i++) {
                p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 0;
                while (str[i + 1 + p[i]] == str[i - 1 - p[i]])
                    p[i]++;
                if (i + p[i] > mx) {
                    mx = i + p[i];
                    id = i;
                }
            }
    
            int maxLen = 0;
            int centerIndex = 0;
    
            for (int i = 1; i < N - 1; i++) {
                if (p[i] > maxLen) {
                    maxLen = p[i];
                    centerIndex = i;
                }
            }
    
            int pos = (centerIndex - 1 - maxLen) / 2;
            return s.substring(pos, pos + maxLen);
        }
    
        private String preProcess(String s) {
           int len = s.length();
           if (len == 0)
              return "^$";
           StringBuffer sb = new StringBuffer("^");
           for (int i = 0; i < len; i++)
              sb.append("#").append(s.charAt(i));
           sb.append("#$");
           return sb.toString();
        }

  • 0
    M

    Can you explain or provide a link for the algorithm?


  • 0
    M

    Looks like O(n^2): while in for loop.


  • 0
    L

    You may just have a search for "Manacher Algorithm", it's a famous O(n) algorithm for Longest Palindromic Substring problem.


Log in to reply
 

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