Java O(n) solution, use Manacher's Algorithm


  • 0
    C

    I will not explain details of Manacher's algorithm because I think I can't do better than some of the online resources, e.g., I find the following video is quite good:
    https://www.youtube.com/watch?v=nbTSfrEfo6M

    public int countSubstrings(String s) {
           
           // Manacher's Algorithm
           int sum = 0;
           
           // boundary case
           if (null == s || 0 == s.length()) return sum;
           // extend the s with extra chars for Manacher's algorithm
           char[] extendArr = preProcess(s);    
           // Manacher's algorithm to count palindromes 
           sum = manachers(extendArr);
           
           return sum + s.length();
       }
       
       private char[] preProcess(String s) {
           
           char[] arr = new char[s.length() * 2 + 3];
    	
    	arr[0] = '@';
    	int index = 1;
    	for (; index < arr.length - 1; index ++) {
    		arr[index] = (index % 2 == 0) ? s.charAt(index / 2 - 1) : '#';
    		
    	}
    	arr[index] = '&';
    	return arr;  
       }
       
       private int manachers(char[] arr) {
           
           int[] indicator = new int[arr.length];
           indicator[0] = indicator[1] = 0;
               
           int centre = 0;
           int right = 0;
           int mirr = 0;
           int sum = 0;
           
           for (int i = 1; i < arr.length - 1; i ++) {
               
               mirr = 2 * centre - i;
               if (i < right) indicator[i] = Math.min(indicator[mirr], indicator[right - i]);
               while (arr[i + (indicator[i] + 1)] == arr[i - (indicator[i] + 1)])
                   indicator[i] ++;
               sum += indicator[i] / 2;
                   
               if (i + indicator[i] > right) {
                   centre = i;
                   right = i + indicator[i];
               } 
           }
           
           return sum;
       }
    

Log in to reply
 

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