My 3ms solution with Manacher algorithm


  • 0
    M

    My solution is using Manacher algorithm. Time is 3ms. Not the fastest.
    The Manacher is O(N) time complexity, so is this algorithm O(N)? I would appreciate it a lot if someone can figure it out.

    class Solution {
    public:
        int countSubstrings(string s) {
            ostringstream os;
    	os<<"#";
    	for(char c : s) {
    		os<<c<<"#";
    	}
    	string ns = os.str();
    	int n = ns.length();
    	int *rl = new int[n];
    	int id = 0, mx = 0;
    	for(int i = 0; i < n; i++) {
    		if(i < mx) rl[i] = min(rl[2 * id - i], mx - i);
    		else rl[i] = 1;
    		//尝试扩展
    		while(i - rl[i] >= 0 && i + rl[i] <= n - 1 && ns[i - rl[i]] == ns[i + rl[i]]) rl[i]++;
    		if(i + rl[i] > mx) {
    			mx = i + rl[i];
    			id = i;
    		}
    	}
    	
    	int ret = 0;
    	for(int i = 0; i < n; i++) {
    		ret += rl[i] / 2;
    	}
    	
    	delete[] rl;
    	return ret;
        }
    };
    

Log in to reply
 

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