You are not logged in. Please login at www.codechef.com to post your questions!

×

Manacher Algorithm

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.

asked 25 Jul '17, 12:36

am10's gravatar image

4★am10
556
accept rate: 0%

edited 25 Jul '17, 19:45


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 :).

link

answered 25 Jul '17, 22:53

liaojh's gravatar image

5★liaojh
1825
accept rate: 7%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×643
×195
×9

question asked: 25 Jul '17, 12:36

question was seen: 485 times

last updated: 25 Jul '17, 22:53