Longest palindromic substring: Difference between revisions

Revision as of 04:28, 13 April 2021

Revision as of 00:59, 23 April 2021

Line 106:

The second case is when the palindrome at MirroredCenter 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 OldCenter, we know the characters before and after it are different. Thus, the palindrome at Center 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 MirroredCenter. For example, if the string was "ababc", the "Old" palindrome could be "bab" with the Center being the second "b" and the MirroredCenter being the first "b". Since the palindrome at the Mirrored Center 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 MirroredCenter extends exactly up to the boarderborder of the "Old" palindrome. In this case, we don't know if the character after the "Old" palindrome might make the palindrome at Center longer than the one at MirroredCenter. But we do know that the palindrome at Center is ''at least'' as long as the one at MirroredCenter. In this case, Radius is initialized to the radius of the palindrome at MirroredCenter and the search starts from there. An example string would be "abcbpbcbp" where the "Old" palindrome is "bcbpbcb" and the Center is on the second "c". The MirroredCenter is the first "c" and it has a longest palindrome of "bcb". The longest palindrome at the Center on the second "c" has to be at least that long and, in this case, is longer.

===Runtime===