这个 PCRE 模式如何检测回文？

Question

这个问题是一个教育演示，展示了在PCRE模式中使用前瞻、嵌套引用和条件语句来匹配所有回文字符串的用法，包括那些不能被PCRE手册中递归模式匹配的字符串。请检查这个PHP片段中的PCRE模式：

$palindrome = '/(?x)
^
  (?:
      (.) (?=
              .*
              (
                \1
                (?(2) \2 | )
              )
              $
          )
  )*
  .?
  \2?
$


/';

这个模式似乎可以检测回文，就像在这个测试用例中看到的一样（也可在ideone.com上查看）：

$tests = array(
  # palindromes
  '',
  'a',
  'aa',
  'aaa',
  'aba',
  'aaaa',
  'abba',
  'aaaaa',
  'abcba',
  'ababa',

  # non-palindromes
  'aab',
  'abab',
  'xyz',
);

foreach ($tests as $test) {
  echo sprintf("%s '%s'\n", preg_match($palindrome, $test), $test);  
}

那么这个模式是如何工作的呢？

---

注释

这个模式使用了 嵌套引用，这是一种类似于 How does this Java regex detect palindromes? 中使用的技术，但与该 Java 模式不同的是，它没有向后查找（但它确实使用了 条件语句）。

此外，请注意 PCRE man page 提供了一个递归模式来匹配一些回文：

# the recursive pattern to detect some palindromes from PCRE man page
^(?:((.)(?1)\2|)|((.)(?3)\4|.))$

这个 man 手册警告说，这个递归模式不能检测到所有的回文字符串（参见：为什么这个递归正则表达式只能在字符重复 2ⁿ - 1 次时匹配？ 和 ideone.com 上的例子），但是这个问题中呈现的嵌套引用/正向先行断言模式可以。

- polygenelubricants

---

我写了这个模式，所以我显然知道它是如何工作的，但我会让其他人来回答它。 - polygenelubricants

我想知道你是在哪里找到所有那些关于正则表达式的技巧的，没想到去 pcre.org 上看 :P - Colin Hebert

@Colin：嵌套引用的内容都是个人研究出来的。我最近才发现了PCRE手册，还没有仔细阅读。 - polygenelubricants

@Colin: java.util.regex.Pattern，MSDN/.NET Framework 4/Regular Expression Language Elements，http://www.regular-expressions.info/。毫无疑问，还有更好的资源可用，但这几乎是我使用的全部资源。 - polygenelubricants

此问题已添加到Stack Overflow正则表达式FAQ，位于“高级Regex-Fu”下。 - aliteralmind

Answer 1

让我们通过构建正则表达式来理解它。首先，回文必须以相反方向相同字符序列开头和结尾：

^(.)(.)(.) ... \3\2\1$

我们希望将这个表达式重写，使得...后面只跟有限长度的模式，这样就可以将其转换为*。使用前瞻即可实现：

^(.)(?=.*\1$)
 (.)(?=.*\2\1$)
 (.)(?=.*\3\2\1$) ...

但仍有不常见的部分。如果我们能够“记录”之前捕获的组呢？如果可能的话，我们可以将其重写为：

^(.)(?=.*(?<record>\1\k<record>)$)   # \1     = \1 + (empty)
 (.)(?=.*(?<record>\2\k<record>)$)   # \2\1   = \2 + \1
 (.)(?=.*(?<record>\3\k<record>)$)   # \3\2\1 = \3 + \2\1
 ...

这可以转换成

^(?: 
    (.)(?=.*(\1\2)$)
 )*

这个方案基本达到目的，但是\2（捕获组）最初并不为空。 它只是无法匹配任何内容。如果记录的捕获组不存在，则需要将其匹配为空。这就是条件表达式出现的原因。

(?(2)\2|)   # matches \2 if it exist, empty otherwise.

所以我们的表达式变成：

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*

现在它匹配了回文的前半部分。第二部分呢？好吧，在匹配了前半部分之后，记录的捕获组 \2 将包含后半部分。所以我们把它放在最后就可以了。

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*\2$

我们也希望考虑奇数长度的回文串。在第一半和第二半之间会有一个自由字符。

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2$

这个方法很好用，但是有一种情况它不能正常工作——当只有一个字符时。这是因为\2没有匹配到任何内容。

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2?$
#      ^ since \2 must be at the end in the look-ahead anyway.

- kennytm

Answer 2

我希望能够提供自己的解决方案。这是我一段时间前编写的正则表达式，用于使用PCRE/PCRE2匹配回文。

^((\w)(((\w)(?5)\5?)*|(?1)|\w?)\2)$

Example: https://regex101.com/r/xvZ1H0/1

- horsefez