×

# Manacher Algorithm

 0 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 d1 (n); int l=0, r=-1; for (int i=0; ir ? 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 4★am10 55●6 accept rate: 0%

 1 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 :). answered 25 Jul '17, 22:53 5★liaojh 182●5 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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