C++ O(n) 3ms manacher algorithm


  • 0
    D

    c++ code:
    manacher algorithm
    time: 3ms
    Time complexity: O(n)
    space : O(n)

    class Solution
    {
    public:
    string longestPalindrome(string s) {
    int len = s.size();
    string r;
    r.resize(2 * len + 2);
    r[0] = '$';
    r[1] = '#';
    int j = 2;
    for (int i = 0; i < len; ++i)
    {
    r[j++] = s[i];
    r[j++] = '#';
    }

        int* p = new int[2 * len + 2];
        int max_len = 0;
        int mm = 0;
        int id = 0;
        int pos = 0;
        for (int i = 1; i < 2 * len + 2; i++)
        {
            if (mm > i)
                p[i] = (mm - i < p[2 * id - i]) ? (mm - i) : (p[2 * id - i]);
            else
                p[i] = 1;
    
            while (r[i - p[i]] == r[i + p[i]])
                p[i]++;
    
            if (i + p[i] > mm)
            {
                id = i;
                mm = i + p[i];
            }
    
            if (p[i] > max_len)
            {
                max_len = p[i];
                pos = i;
            }
        }
    
        string res;
        for (int i = pos - max_len + 2 ; i < pos + max_len ; i += 2)
            res += r[i];
        return res;
    }
    

    };


  • 0
    D

    output in another way : return s.substr((pos - max_len) / 2, max_len - 1);


Log in to reply
 

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