Manachers Algorithm O(n) - 14ms


  • 0
    N
    public String preprocess(String s){
            StringBuilder str = new StringBuilder("#");
            for(char ch:s.toCharArray()){
                str.append(ch).append('#');
            }
            return str.toString();
        }
        public int countSubstrings(String s) {
            if(s==null || s.length()==0)  return 0;
            String T = preprocess(s);
            //manachers algorithm
            int C=0,R=0,count=0;
            int [] P = new int[T.length()];
            for(int i=1;i<T.length()-1;i++){
                int mirror_i = C*2-i;
                P[i] = (i<R)?Math.min(R-i,P[mirror_i]):0;
                while(i+1+P[i]<T.length() && i-1-P[i] >=0 && T.charAt(i+1+P[i])==T.charAt(i-1-P[i])){
                    P[i]++;
                    }
                
                if(i+P[i]>R){
                    C = i;
                    R = i+P[i];
                }
                
                if(P[i]%2!=0)
                    count+=P[i]/2+1;
                else
                    count+=P[i]/2;
            }
           
            return count;
        }
    

    A clear explanation of Manacher's algorithm can be found here.

    http://articles.leetcode.com/longest-palindromic-substring-part-ii/


Log in to reply
 

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