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.