我刚刚看了一个回文问题字谜这导致我一些其他的回文问题。但是，当我觉得一个回文，我想到的是用真实的话，从一门语言，使某种程度的意义上使用该语言现实世界中的回文。

I just read the question Anagram of a Palindrome 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.

所以，如果我们放弃对语法和含义太困难了，我们是一个很好的算法发现，在字典中包含的单词回文？可以pre-过程词典到数据结构，使得它更容易。你不能pre-进程词典通过寻找每一个可能的回文，除非你有办法做到，在计算时间和空间上的真实数量。

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.

假设你想找到回文高达10万字，你有10万小写的英文单词的字典。

Assume you want to find palindromes up to 100,000 characters and you have a dictionary of 100,000 lower case English words.

奖励积分，如果您能想出一个方法来快速找到回文字谜为好。我不知道有这样做，虽然一个可行的办法。

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.

编辑 - 似乎有一些混乱，所以我不能一直清楚。我在找字序列（长度最多为100,000个字符）是回文，而不是单一的字典中的字，这是一个小问题。因此，任何数量的一和多个i的s为palindroms，因为每一个是字和序列是回文。 amanaplanacanalpanama也是一个回文，因为A，人，计划，运河和巴拿马的词（如巴拿马真的是在这个字典）

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)

推荐答案

我在想，如果我真的想有效地查字典在运行时的一些工作，在编译时间为代价的话，我将建立一个状态机检查的字母序列是在词典中。我可以通过读取每个字典条目，然后逐个字母创建一个新的状态，如果一个不存在建立这个。

I was thinking that if I really wanted to efficiently check the dictionary at run time at the expense of some work at compile time then I would build a state machine to check if a sequence of letters was in the dictionary. I could build this by reading each dictionary entry, then letter by letter creating a new state if one didn't exist.

因此​​，如果在字典中的第一个字是一，从开始状态去阅读一个a将是一个有效的过渡一状态。如果下一个字是斧头，我会创建从一个过渡a到上×，斧头，并从斧头到斧头上的e。国家A和斧头将接受国家，也没有开刀。

So, if the first word in the dictionary was "a", going from start state to "a" state on reading an "a" would be a valid transition. If the next word was "axe", I would create a transition from "a" to "ax" on "x", and from "ax" to "axe" on on "e". States "a" and "axe" would be accept states, but not "ax".

此将是一个非确定性状态机，以转换从任何接受将允许（自启动状态读取斧头我可能读一个a后，与axea是在完全串的语言话，可以在字典中找到）。

This would be a non-deterministic state machine, with transitions from any accept to the start state allowed (since after reading "axe" I might read an "a", and "axea" is in the language of strings of complete words that can be found in the dictionary).

我会则状态机优化成一个确定的状态机，使用公知技术（真正使用别人的code，因为这code肯定已经被写入了1000次）。

I would then optimize the state machine into a deterministic state machine using well known techniques (really using somebody else's code, since this code has surely been written over 1,000 times).

在运行时，我会贯穿状态机前锋可能回文，而且，如果它通过向前，向后。

At run time, I would run the possible palindrome through the state machine forwards, and, if it passes forwards, backwards.

我不知道是要找到回文字谜游戏的好方法。

I have no idea what would be a good way to find anagrams of palindromes.