Hi everyone again! Recently, solving the problem 1937 from Timus (by the way, I recommend it to you too! It is a great opportunity to improve yourself in string algorithms), I was faced with the necessity of finding all subpalindromes in the string. Experienced programmers already know that one of the best algorithms for this is Manacher's algo that allows you to get all subpalindromes in compressed form without any additional structures. The only problem — the algorithm is kinda hard to implement. That is, its idea is simple and straightforward, but the implementation usually are heaps of code to the widespread consideration of where to write +1, and where -1.

For those who do not know or do not remember, I will describe briefly the Manacher's algorithm. Conciseness in memory is achieved through the fact that we do not store the indices of palindromes, and for each item in the string we store the half of the length of the largest palindrome, for which item is central. If we are talking about palindromes of even length, we consider the central element to the right of exact center.

Further, we keep the left and the right ends of the rightmost palindrome and, just as it done in the Z-function, we firstly try to initialize the value of the array at this point, using information that is already computed, and then we continue with naive algorithm. To be precise, we can initialize the value of p[i] from the point that is symmetric to it in the rightmost palindrome, i.e. from p[l + (r - i)]. If we talk about palindromes of even length (you already hate them just like me, right?), Then we are interested in the value of p[l + (r - i) + 1]. And yes, it is necessary not to forget that after initialization we should not have to go beyond the known part of the string, i.e. it is necessary to initialize with something that is not more than r - i ( or r - i + 1 for palindromes of even length).

That's how e-maxx offers to use Manacher's algo:

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

Two almost similar pieces of code for palindromes of even and odd length. And, if my memory serves me, and it's still not fixed, they also contain an error (can you find it?)

A little thought and writing out some cases on a piece of paper, I was able to squeeze two separate pieces into one. At the same time, I tried to keep the maximum similarity with the Z-function algorithm.

    vector<vector<int>> p(2,vector<int>(n,0));
    for(int z=0,l=0,r=0;z<2;z++,l=0,r=0)
        for(int i=0;i<n;i++)
        {
            if(i<r) p[z][i]=min(r-i+!z,p[z][l+r-i+!z]);
            while(i-p[z][i]-1>=0 && i+p[z][i]+1-!z<n && s[i-p[z][i]-1]==s[i+p[z][i]+1-!z]) p[z][i]++;
            if(i+p[z][i]-!z>r) l=i-p[z][i],r=i+p[z][i]-!z;
        }
    }

However, long enough string with while spoils the whole picture. I propose to fight with it like this:

    vector<vector<int>> p(2,vector<int>(n,0));
    for(int z=0,l=0,r=0;z<2;z++,l=0,r=0)
        for(int i=0;i<n;i++)
        {
            if(i<r) p[z][i]=min(r-i+!z,p[z][l+r-i+!z]);
            int L=i-p[z][i], R=i+p[z][i]-!z;
            while(L-1>=0 && R+1<n && s[L-1]==s[R+1]) p[z][i]++,L--,R++;
            if(R>r) l=L,r=R;
        }

As it seems to me, this is the most readable version of the code. And what do you think about this? How to implement Manacher's algo least painful? And in general, how do you solve the problem of finding all subpalindromes in the string? Share your ideas in the comments below :)

P.S. It looks like my English is especially poor in this entry. My apologies about it :(

UPD: droptable said in the comments on how to support arrays from Manacher's algorithm in online. Here I put an example of the algorithm itself, with some modifications, which will be discussed below.

The basic idea of ​​the algorithm: at any time we keep the center of the longest palindrome relating to the right end of the line. When we add character to the end, we have two options for what happens next:

1. Main palindrome expands. Then we simply increase its radius value and return.
2. Main palindrome not expands. This means that we will need to traverse an array forward to find new primary palindrome. Thus, each time a new cell initializing with number in the cell that is symmetrical to the center of the previous main palindrome. Once it turned out that we can extend the current palindrome, which means that it is leftmost of the related to the end of the string and then it will become the new main palindrome.

Now about the changes in the code. First, were deleted the two empty characters that were inserted into the string at the begin. As it turned out, they are not necessary, however, but their addition to their complexity algorithm.

Second, was added get(). Mikhail mentioned in his comment about some problems with online. The problem was that, in any moment, we know only the final values ​​in the elements, which are earlier than the center of the main palindrome. However, you will notice that the values ​​after it, we can get in O(1) if we will refer to symmetric from the center of the main palindrome element.