Manacher Algorithm

general
, ,
1

I was going through this blog, in order to understand the manacher blog, but i was unable to get the implementation part of it for odd length palindrome. I am adding the code for that part.

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;
}

I was testing this on string s = “abxbac” and the array d1[] = {1,1,3,2,1,1} (formed by this logic),and i am not getting how d1[3] = 2 (0 - based indexing) it should be 1. Can anybody help me to understand this.

2

Delete that + 1 at the end of what int k equals and you’re good to go. Honestly though, I don’t really like this implementation due to how possibly buggy it may get, and I used this blog instead for understanding the construction better. Experiment more and build your own :).

1 Like