# Palindrome finder: help find ways to speed up?

Mike C. Fletcher mcfletch at rogers.com
Tue Apr 8 23:48:59 CEST 2003

```Here's an algorithm that should give you a decent speedup (it's based on
the suggestions that I _think_ Steven was giving you)...

words = [...]
backwardMap = {...} # last-char to reversed word-list, construct from words

for word in words:
for back in backwardMap[ word[-1]]:
subset = min(len(word),len(back))
if word[:subset] == back[:subset]:
good_chance_you_have_one_so_explore_further()

For even faster operation, pre-calculate and store the word-lengths in
the backwardMap so that you don't have to calculate them each time.

Basically, this should reduce the search space to 1/64th of total (or
so) for each word with a simple O(1) hash-table lookup, with each check
considerably faster in exchange for an O(n) setup fee (reversing and
taking the length of each word, then adding to the dictionary).  Key is
setting up the correct data-structures so that when you're doing the
actual run-time searches you can rapidly whittle down the search space
to a reaidly-processed sub-set.  You see the same thing in fuzzy-text
searching, BTW.

You can also do neat things such as using the tails beyond subset to
lookup third/fourth words in the middle (you need a forward map to make
that work efficiently, of course).  Keep in mind that if you find a
palindrome set which exactly matches on both sides you get the
possibility of having an inifinite sequence of those nesting in, so
you'll want a mechanism to stop that at some point :) .

Enjoy,
Mike

Jon Brown wrote:

>Steven,
>
>Actually the program does exactly what you describe, except from the inside
>out because it starts in the middle, and it cuts out of the loop if the
>characters don't match.
>
>To look for pals it spins off big, big numbers of combinations, true enough.
>That's what behind the need for speed. Since Python is inherently on the
>pokey side, I expected the slowness but wonder if I'm missing a cool way to
>pick up the pace. But I suspect the solution will involve C++, and I've
>
>Jonedary
>
>
>
>>A smarter search would do better.  One approach would be to build
>>the palindrome from both ends instead of from just one end.  For
>>example, suppose your code understood that a palindrome starting
>>with 'orange' must end with a word 'o', 'ro', 'aro', 'naro',
>>'gnaro', 'egnaro', or a word ending with 'egnaro'.  If there are
>>no such words, it can skip 1/n of the search space, namely all the
>>
>>
_______________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://members.rogers.com/mcfletch/

```