Hello, this is a brief post about extending Manacher's algorithm to get the longest palindromic substring ending at every position while maintaining its $$$\mathcal{O}(n)$$$ complexity, in response to an old blog post asking for the same thing with no clear answers, and the recently added All Palindromes problem on CSES.

Say we already computed the d Manacher array in $$$\mathcal{O}(n)$$$ using the following algorithm:

vector<int> manacher(string& t) {
    string s{'$'};
    for(const char& c: t) s += string{'#', c};
    s += string{'#', '^'};

    vector<int> d((int)s.size());
    int l = 1, r = 1;
    for(int i = 1; i < (int)s.size() - 1; ++i){
        d[i] = max(0, min(r - i, d[l + r - i]));
        while(s[i - d[i]] == s[i + d[i]]) ++d[i];
        if(i + d[i] > r){
            l = i - d[i];
            r = i + d[i];
        }
    }
    return d;
}

We now want to compute an array res where res[i](initially $$$0$$$) is the length of longest palindromic substring ending at index $$$i$$$.

First considering only oddly-sized substrings, if we know that the longest palindromic substring centered at $$$i$$$ is $$$t[i-r:i+r]$$$, then we can simply apply res[j] = max(res[j], 2 * (j - i) + 1)) for every $$$j=i,...,i+r$$$ as the substring centered at $$$i$$$ ending at $$$j$$$ is also palindromic but this takes $$$\mathcal{O}(n^2)$$$ time as we must do this for every $$$i=0,1,...,n-1$$$.

An important observation is that res[j] will only change once at some $$$i$$$, as at any $$$i' \gt i:2(j-i')+1 \lt 2(j-i)+1$$$. Since we are updating res[j] in increasing order of j, we can simply keep a pointer to the first index of res that has not been updated yet, from which we start updating. This results in an $$$\mathcal{O}(n)$$$ complexity algorithm.

The same logic can be applied to evenly-sized substrings, so we loop again in order to count their contribution.

The final algorithm is the following:

vector<int> longest_palindrome_ending(vector<int>& d) {
    int n = ((int)d.size() - 3) >> 1, j = 0;
    vector<int> res(n);
    for(int i = 0; i < n; ++i)
        for(j = max(j, i); j < i + (d[(i + 1) << 1] >> 1); ++j)
            res[j] = 1 + ((j - i) << 1); 
    j = 0;
    for(int i = 1; i < n; ++i)
        for(j = max(j, i); j < i + (d[1 + (i << 1)] >> 1); ++j)
            res[j] = max(res[j], (j - i + 1) << 1);
    return res;
}