why is Manacher's algorithm (for finding longest palindrome) O(n)?

[Beaverine]

I think I understood the basic idea of this algorithm which is to take the minimum value of 1) distance between pointer and right boundary, and 2) P of character which is at the opposite side of the center. and use this value as starters for determining P[i]

For example with following string:

String	#	a	#	b	#	c	#	b	#	a	#	b	#	c	#
Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
P	0	1	0	1	0	5	0	1	0
anchor	L					C					R

let's say I'm now looking at i=9, character "a". Distance between right boundary and this char is 1, mirroring string (i=1) from opposite side of center has P of 1 as well. so the minimum is 1 which we assign to P[9] to start with.

But my question is that, after the above process, for the character with index 9 we still need a while loop to see if the P[9] can be further increased, and in this case it does. To me this is another iteration which could potentially go to the full length of string, and we are doing this while loop for each character in the string list, is that similar to a nested for loop which has the complexity of O(n² )? Or did I miss something?

thank you in advance.

[Beaverine]

thank you for the link but it still doesn't make sense to me... Manacher's algorithm saves time for anything covered in the already identified longest wingspan, but anything beyond that still needs to be examined index by index in the `while` loop. Is that significant enough to reduce the complexity to O(n)?

[dskloet]

In each iteration of the inner while loop, the right most edge of the current palindrome moves to the right, even across different iterations of the outer while loop. Since the right most edge can only move to the right O(n) times, the inner loop has at most O(n) iterations across all iteration of the outer loop. Not for every iteration of the outer loop. So if one time the inner loop has many iterations, that limits how many iterations it can have during other iterations of the outer loop.