查找回文的正则表达式表现奇怪

Question

我想写一个程序来找出回文（就是从头到尾读和从尾到头读都一样的词，比如 anna）。

而且这个程序还应该能处理多个单词，比如 car a rac，以及句子中的回文，比如 asdcar a racbnm。

我写了一个正则表达式来找到回文的起始位置：

([a-z])(\s*)[a-z]?(\\2)(\\1)

这个表达式会先找到一个字母，然后可以有空格，再找到另一个字母，接着又可以有空格，最后再找到第一个字母。

这个方法运行得不错，但对于字符串 xxxxx，它的表现就有点奇怪：

import re
p = re.compile('([a-z])(\s*)[a-z]?(\\2)(\\1)')
finds = p.finditer('xxxxx')
for m in finds:
    print m.span()

输出结果

(0, 3)
(3, 5)

它没有找到我想要的那个位置：(1, 4)

我的正则表达式哪里出问题了？

补充说明：它应该只找到回文的起始位置，后面的处理会由算法来完成。

Answer 1

你的正则表达式无法匹配重叠的部分（如果想要做到这一点，你需要使用带捕获组的前瞻来进行一些调整）。

这个表达式首先匹配前面三个x字符；它的匹配过程是：

• 匹配一个字符（组1），零个空格（组2），一个可选字符（?是贪婪的），再加上组2的零个空格，最后是组1的一个字符。

第二次匹配必须在第一次匹配之后开始；两个xx字符能够匹配，因为[a-z]?这个模式是可选的。

一般来说，你无法创建一个正则表达式来匹配回文（至少在Python的re引擎中是这样），因为没有办法反向匹配任意宽度的前一个组。