How to enhance my 8ms Manacher solution of c++? Only beats 78.94%


  • -1
    G
    class Solution {
    public:
    	string longestPalindrome(string s) {
    		int len = s.length();
    
    		if (len == 0) {
    			return "";
    		}
    
    		if (len == 1) {
    			return s;
    		}
    
    		string ss("$");
    		ss.reserve(2 * (len + 1));
    		for (auto it = s.begin(); it != s.end(); ++it) {
    			ss.push_back('#');
    			ss.push_back(*it);
    		}
    		ss.push_back('#');
    
    		std::vector<int> p(ss.size(), 1);
    
    		int mx = 0;
    		int max = 1;
    		int id;
    		int middle = 0;
    
    		len = ss.size();
    		for (int i = 1; i < len; ++i) {
    			if (mx > i) {
    				p[i] = std::min(p[2 * id - i], mx - i);
    			}
    			else {
    				p[i] = 1;
    			}
    
    			while (ss[i - p[i]] == ss[i + p[i]]) {
    				p[i]++;
    			}
    
    			if (p[i] + i > mx) {
    				mx = p[i] + i;
    				id = i;				
    			}
    
    			if (p[i] > max) {
    				max = p[i];
    				if (ss[i] == '#') {
    					middle = i / 2;
    				}
    				else {
    					middle = i / 2 - 1;
    				}
    			}
    		}
    		max--;
    		return s.substr(middle - max / 2, max);
    	}
    };

Log in to reply
 

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