Longest palindromic substring: Difference between revisions

Revision as of 03:36, 6 July 2021

Revision as of 20:44, 14 October 2021

Line 102:

Manacher's algorithm is faster because it reuses precomputed data when a palindrome exists inside another palindrome. There are 3 cases of this. They are represented by the "if / else if / else" statement in the pseudocode.

The first case is when the palindrome at <code>MirroredCenter</code> lies completely inside the "Old" palindrome. In this situation, the palindrome at <code>Center</code> will have the same length as the one at <code>MirroredCenter</code>. For example, if the "Old" palindrome is "abcbpbcba", we can see that the palindrome centered on "c" after the "p" must have the same length as the palindrome centered on the "c" before the "p".

The second case is when the palindrome at <code>MirroredCenter</code> extends outside the "Old" palindrome. That is, it extends "to the left" (or, contains characters with a lower index than any inside the "Old" palindrome). Because the "Old" palindrome is the largest possible palindrome centered on <code>OldCenter</code>, we know the characters before and after it are different. Thus, the palindrome at <code>Center</code> will run exactly up to the border of the "Old" palindrome, because the next character will be different than the one inside the palindrome at <code>MirroredCenter</code>. For example, if the string was "ababc", the "Old" palindrome could be "bab" with the <code>Center</code> being the second "b" and the <code>MirroredCenter</code> being the first "b". Since the palindrome at the Mirrored Center<code>MirroredCenter</code> is "aba" and extends beyond the boundaries of the "Old" palindrome, we know the longest palindrome at the second "b" can only extend up to the border of the "Old" palindrome. We know this because if the character after the "Old" palindrome had been an "a" instead of a "c", the "Old" palindrome would have been longer.

The third and last case is when the palindrome at <code>MirroredCenter</code> extends exactly up to the border of the "Old" palindrome. In this case, we don't know if the character after the "Old" palindrome might make the palindrome at <code>Center</code> longer than the one at <code>MirroredCenter</code>. But we do know that the palindrome at <code>Center</code> is ''at least'' as long as the one at <code>MirroredCenter</code>. In this case, <code>Radius</code> is initialized to the radius of the palindrome at <code>MirroredCenter</code> and the search starts from there. An example string would be "abcbpbcbp" where the "Old" palindrome is "bcbpbcb" and the <code>Center</code> is on the second "c". The <code>MirroredCenter</code> is the first "c" and it has a longest palindrome of "bcb". The longest palindrome at the <code>Center</code> on the second "c" has to be at least that long and, in this case, is longer.

===Runtime===