Robert_Alonso_29's blog

Is this a bug in e-maxx manacher algorithm implementation?
By Robert_Alonso_29, 9 years ago, In English

Hi everyone. I've been learning the manacher algorithm for finding the longest palindromic substring these days, and when I started to practice with the implementation I found on http://e-maxx.ru/algo/palindromes_count, the result I got was okay in every vector value except a single one for a small test case.

I tried this code, which, as the description says, takes care of the odd-length subpalindromes

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

Then I tried the test case where s="xxxxxxxaxxx", and the resulting vector d1 was d1[] = {1,2,3,4,3,2,1,4,3,2,1}

However, the last 3 in d1 would be wrong, because it intends to say that the longest palindrome with center at index 8 is "xaxxx" with length d1[8]*2-1 = 3*2-1 = 5.

Does this say that there is a bug in this implementation? I hope that's not the case. I've directly copied and pasted the code I found on e-maxx. Please check it out, thank you.

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

(wrong)

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

There is indeed a bug in the implementation. It is pointed out in the comments section in the first comment. What it says is basically

replace int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;

with int k = (i>r ? 1 : min (d1[l+r-i], r-i));

→ Reply