C++ O(n) using Manacher


  • 0
    J
    
    class Solution {
    public:
        int Manacher(string s) {
            const char kNullChar = '\0';
            string str = string(1, kNullChar);
    
            for(auto c: s) str += string(1, c) + kNullChar;
    
            string max_str = "";
            int len = str.size();
            int right = 0;
            int center = 0;
            vector<int> dp(len, 0);
    
            for(int i = 1; i < len; i++) {
                int mirr = 2*center - i;
    
                // i is within right so can take the minimum of the mirror or distance from right
                if(i < right) {
                    dp[i] = min(right - i, dp[mirr]);
                }
    
                // keep expanding around i while it is the same and increment P[i]
                int left_index = i - (1 + dp[i]);
                int right_index = i + (1 + dp[i]);
                while(left_index != -1 && right_index != len && str[left_index] == str[right_index]) {
                    left_index--;
                    right_index++;
                    dp[i]++;
                }
    
                // i goes beyond current right so it is the new center
                if(i + dp[i] > right) {
                    center = i;
                    right = i + dp[i];
                }
            }
            
            int count = 0;
            for(int i = 0; i < len; i++) {
                count += ceil((double)dp[i]/2.0);
            }
            return count;
        }
    
        int countSubstrings(string s) {
            return Manacher(s);
        }
    };
    

Log in to reply
 

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