World's Longest Palindrome? - The Algorithm

The algorithm I used to create the world's longest palindrome (?) 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. Color it red: aca. Since this 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. Choose one and add it to the left. Remember the others for later. In my example, the program chose a caddy. Now identify the bits of that that are left over, 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:
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 remaining bit, 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 (including 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.

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