Manacher's algorithm (unable to understand)

1

I was going through the editorial at cp algorithms and was unable to understand the implementation please help me.
link : Manacher's Algorithm - Finding all sub-palindromes in O(N) - Algorithms for Competitive Programming

vector<int> d1(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 (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
        k++;
    }
    d1[i] = k--;
    if (i + k > r) {
        l = i - k;
        r = i + k;
    }
}

//---------------------------------------------------------------------

vector<int> d2(n);
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 (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
        k++;
    }
    d2[i] = k--;
    if (i + k > r) {
        l = i - k - 1;
        r = i + k ;
    }
}
2

Figure out what’s happening and then you will be able to code it by yourself :slight_smile: .
Tbh, It’s much easier to code this by yourself than to understand it.

l and r are the indexes of the palindrome we found with the largest value of r.

if i is already in front of r, then we are forced to start from 1. Otherwise, we can use the other part of the palindrome to figure out the answer, since the palindrome length will be the same, at least inside the palindrome.

If the inner palindrome is completely inside, the second while loop will break immediately, because we already know that it didn’t extend for the value on the
other side.

If it extends, that means it’s at the edge and the value of r will increase.

We need to do it two times for both odd and even length palindromes.

There are a lot of “off by 1” you can make here which is why I recommend try coding it by yourself once.

3

oh thanks I was able to come up with the solution:

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    string t;
    cin>>t;
    int n=t.length(),c=0,r=0;
    n=2*n+1;
    int p[n]={0};
    p[0]=0;
    p[1]=1;
    for(int i=2;i<n;i++)
    {
        int mir=2*c-i;
        if(i<r)
        {
            p[i]=min(r-i,p[mir]);
        }
        while( ((i + p[i]) < n && (i - p[i]) > 0) &&  ( ((i + p[i] + 1) % 2 == 0) ||  
            (t[(i + p[i] + 1)/2] == t[(i - p[i] - 1)/2] )))
        {
            p[i]++;
        }
        if(i+p[i]>r)
        {
            c=i;
            r=i+p[i];
        }
    }
    for(int y:p)
    {
        cout<<y<<" ";
    }
    return 0;
}