title: Finding palindromes of real words
body: <p>I just read the question <a href="https://stackoverflow.com/questions/8447222/anagram-of-a-palindrome">Anagram of a Palindrome</a> which lead me to some other palindrome questions.  But when I think of a palindrome, I think of real world palindromes that use real words from a language and make some degree of sense in that language.</p>
  
  <p>So, if we give up on grammar and meaning as too difficult, what we be a good algorithm for finding palindromes that are comprised of words in a dictionary?  You can pre-process the dictionary into a data structure that makes it easier.  You can't pre-process the dictionary by finding every possible palindrome, unless you've got a way to do that in a realistic amount of computing time and space.</p>
  
  <p>Assume you want to find palindromes up to 100,000 characters and you have a dictionary of 100,000 lower case English words.</p>
  
  <p>Bonus points if you can come up with a way to quickly find anagrams of palindromes as well.  I'm not sure there is a feasible way to do that though.</p>
  
  <p>Edit - there seems to be some confusion, so I must not have been clear enough.  I'm looking for sequences of words (up to 100,000 characters in length) that are palindromes, not single dictionary words, which is a trivial problem.  So, any number of "a"s or "i"s are palindroms, since each one is word and the sequence is a palindrome. "amanaplanacanalpanama" is also a palindrome, because "a", "man", "plan", "canal", and "panama" are words (if "panama" is really in this dictionary)</p>