How to choose the next center in the longest palindrome algorithm?

Question

This is a question about the longest palindrome algorithm discussed here some time ago. The quoted blog post, which explains the algorithm, says: "to pick the next center, take the center of the longest palindromic proper suffix of the current palindrome". Unfortunately, they don't provide a proof and I don't really understand why the next center is the center of the longest palindromic proper suffix of the current palindrome.

Can anybody prove/explain it ?

Answer 1

So we're moving to the right...

Say your "current" palindrome is 40 letters big. (Maybe centered on say position 100.) You're trying to find a bigger one.

(OK, there might be a bigger one that is 900 letters long, and that is 50,000 letters to the right -- totally uninvolved with this one. That's fine. But we'll get to that in the future. For now, we have to move the center to the right while looking for longer-than-40 palindromes. Makes sense?)

So we have to move to the right - we could move one step. BUT we want to move as far as possible without missing any.

Now, if the next one to the right is going to include this one...in fact, it has to include the right-most letter of this group of 40. (It can't be further to the left, as we've already checked, so, it must center after 100, and, because it's going to be longer than 40, it must include our right-hand letter, #120.)

So how far back do we have to go?

Well, you can't go back (from 120) further than a palindrome! If it's not a palindrome in the middle it will never be a palindrome.

3333333333333331110111

You can only go "back" to the 0. the 1 sitting to the left of the 0 (for example), could never be a palindrome.

So it's that simple. You have to include our rightmost letter (if we're going to include any of us at all), and, you want it to be as big as possible, and it has to be a palindrome because palindromes can only start (I mean "from the middle") with palindromes.

in the example above it's not possible that the 1 to the left or the 0, or let's say the right-most 3, could ever in this universe center a palindrome, no matter what we later find on the right. They don't have palindromes around them, so they could "never be" a palindrome center!

Note that the 3 in the middle of the 3s could possibly center a bigger palindrome .... but don't forget we've already checked this is the longest palindrome so far (based on centers, from the left), so that cannot be true.

So any palindrome that is longer than this one -- rather, the next possible starting point for a palindrome longer than this one -- is that 0.

In other words, it's simply the center of the biggest palindrome we currently have at the right. (so, not the "111" which is a palindrome but short, but the "1110111" which is the longest palindrome you can see stuck on the right.)

Indeed, the two possibilities we have to check are (A) the "0" and (B) the "1" at the second-last spot. of course, among those two possibilties, we have to go from left to right, so (A) the "0" is indeed the next one to check.

Don't forget those two (the 0 and the 1 in question) are equivalent to saying "there's a palindrome 1110111 stuck to the end, and there's a shorter palindrome 111 stuck to the end".

Of course 1110111 is longer, so the center of 1110111 is obviously to the left of the center of 111.

The longest palindrome stuck to the right, will of course have the center closest the left.

So hopefully that makes clear JUST the specific part of the discussion on the linked blog, which, you asked about!!! I deliberately repeated myself in a number of ways, hopefully it helps. It's Jungian algorithms day :)

Again please note I am specifically and only trying to clarify the very specific issue Michael asked about.

Bloody confusing eh?

BTW, I simply ignored the issue of on-character off-character centers - but it is irrelevant to understanding what you asked about.