C++ O(n) time solution, 8ms beats 80%, using Manacher algorithm


  • 0
    I

    This algorithm is hard to understand for me, not even mention to explain it......
    Here's a link: http://articles.leetcode.com/longest-palindromic-substring-part-ii/

    string longestPalindrome(string s) {
        if (s.empty()) return "";
        string str(s.size() * 2 + 1, '#');
        for (int i = 1; i < str.size(); i += 2) { str[i] = s[i / 2]; }
        vector<int> P(str.size(), 0);
        int maxLen = 1, j = 1, maxIndex = 1;
        P[1] = 1;
        for (int i = 2, size = str.size(); i < size; i++) {
    	    int exBound = min(i, size - i - 1);
    	    int exLen = min(P[2 * j - i], P[j] - i + j);
    	    while (exLen < exBound && str[i + exLen + 1] == str[i - exLen - 1]) { exLen++; }
    	    if (exLen > maxLen) {
    		    maxIndex = i;
    		    maxLen = exLen;
    	    }
    	    P[i] = exLen;
    	    if (i + exLen > j + P[j]) { j = i; };
        }
        string res(maxLen, 0);
        int middleIdx = maxLen / 2;
        if (str[maxIndex] == '#') {
    	    for (int i = 0; i < maxLen / 2; i++) {
    		    res[middleIdx + i] = res[middleIdx - 1 - i] = str[maxIndex - i * 2 - 1];
    	    }
        } else {
    	    for (int i = 0; i < maxLen / 2 + 1; i++) {
    		    res[middleIdx + i] = res[middleIdx - i] = str[maxIndex - i * 2];
    	    }
        }
        return res;
    }

Log in to reply
 

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