回文是一种有趣的文本形式，它正读和反读都是相同的。从年轻时第一次看到著名的“Madam, I'm Adam”和“A man, a plan, a canal, Panama!”回文开始，就对它们产生了浓厚的兴趣。手工制作回文是一件费力的事情，所以当发现可以让计算机来做这项工作时，非常感兴趣。第一次看到计算机生成的回文是在Peter van der Linden 1994年的《Expert C Programming》第4章，他展示了一个近300字的回文。虽然van der Linden的书没有提供生成回文的代码，而是将其作为一个练习，但早期尝试用C语言编写回文生成器时，尝试是笨拙且效率低下的。幸运的是，Norvig的算法既优雅又直接，易于在C#中实现。让看看它是如何工作的。
在深入算法细节之前，想先描述一下read_dict()方法。它读取包含每行一个单词或短语的字典文件到两个List中。一个列表(_fw)包含了原始顺序的单词，第二个列表(_bw)包含了单词的反转，例如"cat"被存储为"tac"。reverse()方法用于反转一个String。对Norvig的read_dict()方法做了一点修改，允许从给定的起始和结束行号读取。顺便说一下，这展示了C#中一个经常被忽视的特性，即可选参数。提供了一个比Norvig提供的npDict.txt字典小得多的版本，叫做npdictPeterVanDerLinden.txt。npdictPeterVanDerLinden.txt中的单词来自van der Linden的书，并且被优化以快速生成几个回文。（诚然，这些回文通常没有意义，但这个程序的重点是算法。）
在App.config中设置想要使用的字典文件的名称，例如：
<setting name="Dictionary" serializeAs="String">
<value>C:\MyDocuments\Palindrome\Dictionary\npdict.txt</value>
</setting>
PalPython类有两个String列表，一个用于构建回文的左侧，一个用于构建右侧。
public List<String> left { get; set; }
public List<String> right { get; set; }
在init()方法中，首先创建由"A man, a plan, a canal, Panama"组成的"种子"单词。（程序运行时，将忽略标点和空格。参见canonical()方法了解这是如何完成的。实际上还存储了右侧的单词，并且单词中的字母也被反转了。）将"amanaplan"放在left中，将"acanalpanama"放在right中。
接下来，找到另一侧文本不匹配的子字符串。在下面的表中，子字符串（本身是一个回文），aca在右侧，并在下面的表中加粗显示：
left right
amanaplan aca
nalpanama
接下来，在字典中搜索以子字符串aca开头的单词，并使用extend()方法将其添加到左侧。假设选择了短语a catnip，如前所述，它被存储时没有空格，即acatnip。将其添加到左侧，然后再次找到另一侧文本不匹配的子字符串。在下面的表中，子字符串tnip在左侧，并在下面的表中加粗显示：
left right
amanaplanaca tnip
acanalpanama
由于tnip不是一个回文，需要在字典中找到以pint（tnip的反转）结尾的单词。假设从字典中获取了apint。使用extend()方法将其添加到右侧，观察到子字符串，仅仅是字母a，是一个回文，瞧，找到了一个回文（尽管是一个愚蠢的）：
A man, a plan, a catnip, a pint, a canal, Panama!
但是，如果在获取第二个单词后没有得到一个回文怎么办？这就是Norvig出色的backtrack()方法发挥作用的地方。假设字典有acatalpa、acaret和abater（A Catalpa是一种树；Caret是键盘上数字6上面的符号，Bater是一个制革工人。）现在当尝试匹配子字符串aca时，两个匹配aca的单词acatalpa和acaret被放在了栈上（下面描述）。在下面的表中，添加了acatalpa到左侧（参见extend()方法了解详情）。
left right
amanaplanaca talpa
acanalpanama
但是字典中没有以aplat（子字符串talpa的反转）结尾的单词。所以backtrack，从left中移除acatalpa，尝试下一个acaret，通过在search()中弹出它，并使用extend()将其添加到左侧。
left right
amanaplanaca ret
acanalpanama
现在在字典中寻找以ter（子字符串ret的反转）结尾的单词。获取了abater并将其添加到右侧。
left right
amanaplanaca ret
abater
acanalpanama
现在子字符串是aba（它本身是一个回文），瞧，找到了另一个回文：
A man, a plan, a caret, a bater, a canal, Panama!
当找到回文时，它们被写入一个名为pallog
下载并解压项目，并用Visual Studio打开Palindrome.sln。它由两个项目组成：
通过按F6构建解决方案。记得按照上面描述的设置想要使用的字典文件的名称。
PalPython类是主类，它有一些属性，包括两个Dictionary项。
public Dictionary<String, String> _truename, 它保存了一个规范化单词的真实名称，和
public Dictionary<String, int> seen, 它跟踪一个单词是否被用来构建当前的回文。
在PalPython中使用的关键类是MyStackItem。它由当前子字符串和匹配它的单词组成，这些单词存储在Stack中。一个MyStackItem的栈被保存在它们自己的栈中，public Stack<MyStackItem>wordStack。当程序运行时，子字符串和匹配它的单词被放在一个MyStackItem对象中，然后该对象被推到wordStack上。这个类本身非常简单，只有两个属性；实际上，用于调试的PrintStack(), PrintWords(), 和 ToString()方法实际上是类中最复杂的部分！很快就会看到PrintStack()和PrintWords()。
public class MyStackItem
{
public String Substring { get; set; }
public Stack<String> Words { get; set; }
...
}
当在Python（使用的是IDLE版本2.7）中使用调试器时，在search()方法调用self.extend()后添加了以下内容，以打印当前匹配子字符串的单词列表和当前栈：
print (words)
print (self.stack)
例如，对于子字符串aca（使用npdictPeterVanDerLinden.txt字典文件），这是IDLE的Python shell中的输出：
['acalamus', 'acanal', 'acaret', 'acat', 'acat', 'acatalpa', 'acatnip', 'acaw']
[('aca', ['acalamus', 'acanal', 'acaret', 'acat', 'acat', 'acatalpa', 'acatnip', 'acaw'])]
MyStackItem类中的PrintWords()和PrintStack()方法生成相同的输出。使用之前的例子，在回溯单词catalpa之后，栈在Pop()之前看起来像这样：
[('aca', ['acanal', 'acaret'])], [('talpa', [])]
在search()方法中的Pop()之后，talpa被移除，因为它没有匹配的单词，由空方括号([])表示：
[('aca', ['acanal', 'acaret'])]
当使用npdict.txt字典文件运行Palindrome.exe的Release版本时，这里有一些结果：