World's Longest Palindrome? - The Algorithm

The algorithm I used to create the world's longest palindrome (versions 1 and 2) is as follows:
(1) Start off with the following seed text, divided into a left and right half:
A man, a plan, a canal, Panama

(2) Find the bit that is not palindromic; that is, not matched by text on the other side. Call that the remainder and color it red: aca. Since the remainder is itself a palindrome, the whole enchilada must be a palindrome. Record it as such, but keep going to try and find a longer one.
A man, a plan, a canal, Panama

(3) Look in the dictionary for words or phrases that begin with aca. Randomly choose one and add it to the left. Remember the others for later. In my example, the program chose a caddy. Identify the remainder again, namely ddy:
A man, a plan, a caddy, a canal, Panama

(4) Now find in the dictionary a word that ends with ydd (the reverse of ddy). The program found Roydd, which is a male first name (although far from a common one). Add it to the right, leaving the remainder Ro:
A man, a plan, a caddy, Roydd, a canal, Panama

(5) Now we need a word starting with or (the reverse of Ro) on the left. The program chose Ore. The remainder, e, is a palindrome, so again we've got a winner. Print it to a file and move on.
A man, a plan, a caddy, Ore, Roydd, a canal, Panama

(6) Keep going back and forth in this fashion, until you have 10 or 15 thousand words. However, at some point we may need to backtrack. For example, suppose the program next chose Belize:
A man, a plan, a caddy, Ore, Belize, Roydd, a canal, Panama

(7) We need a word on the left that starts with zileb, but there is no such word in my dictionary. So we backtrack, erasing Belize and trying another word that ends in e. Fortunately, there are many of these. If there were not, we would have to backtrack another step and erase Ore, replacing it with another word that starts with or.

There are a few more technical details. For example, whenever I choose a word, I need to record it so that I don't use it again (but un-record it when backtracking over it). For the other details, see the program listing, or go back to the palindrome itself.

The Algorithm, Version 3

For version 3, I switched to a letter-by-letter approach, rather than phrase-by-phrase. I keep track, on both left and right, of the phrases that have been completed, as well as a currently-being-worked-on phrase (one on the left and one on the right) that are not yet complete. These are the two middlemost phrases. So, it might go like this:
(1) Start off with the following seed text, divided into left and right halves, with incomplete phrases in the middle (in this case, the incomplete "aca" on the left, and no incomplete letters on the right). We always maintain the invariant that the concatenation of the letters on the left equals the reverse of the concatenation of the letters on the right (including the letters in any incomplete phrase).
A man, a plan, aca a canal, Panama

(2) Choose a letter to add to both the left and right. I will choose the word that gives the highest number of completed prefixes on the left and suffixes on the right. It turns out this is the letter r:
A man, a plan, acar r a canal, Panama

(3) Again, add the letter that completes the most prefixes and suffixes; in this case e:
A man, a plan, acare er a canal, Panama

(4) At this point we could add another letter, or we could mark the phrase "acare" ("a care") as complete, moving it the completed part of the left-hand-side:
A man, a plan, a care er a canal, Panama

(5) Keep going like this, adding letters, and sometimes moving a current string of letters to the completed phrase list (on either left or right). Just as in the previous version of the algorithm, at some point we may have to backtrack, undoing some moves we have made, and making an alternative choice instead.

Peter Norvig, 20:02 02/20 2002 See some comments on this page.