← all categories

Manacher 4b8194e7

Manacher's algorithm: longest palindromic substring centered at every position, both odd and even length, in linear time. d1[i] = radius of the longest odd-length palindrome centered at i (length 2*d1[i]-1); d2[i] = radius of the longest even-length palindrome centered between i-1 and i (length 2*d2[i]).

Time: O(n). tested

content/strings/manacher.h

pair<vector<int>, vector<int>> manacher(string &s) {
    int n = (int)s.size();
    vector<int> d1(n), d2(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) k++;
        d2[i] = k;
        if (i + k - 1 > r) { l = i - k; r = i + k - 1; }
    }
    return {d1, d2};
}