20

这个问题是关于在 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);  
}

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

笔记

此模式使用嵌套引用，这与此 Java 正则表达式如何检测回文？，但与 Java 模式不同的是，它没有后视（但它确实使用了条件）。

另外，请注意 PCRE手册页提供了一个递归模式来匹配一些回文：

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

手册页警告说这种递归模式不能检测所有回文（参见：Why will this recursive regex only match when a character repeats 2 n - 1 times? and also on ideone.com），但嵌套的参考/正向前瞻模式呈现在这个问题上可以。

4

2 回答 2

28

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

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

我们想重写它，使得...后面只有有限长度的模式，这样我们就有可能将它转换成 a *。这可以通过前瞻来实现：

^(.)(?=.*\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$

这很好用，除了在一种情况下——只有 1 个字符。这又是由于\2没有匹配。所以

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2?$
#      ^ since \2 must be at the end in the look-ahead anyway.
于 2010-09-19T20:56:09.493 回答
1

我想提出我自己的解决方案。这是我不久前编写的一个正则表达式，用于使用 PCRE/PCRE2 解决匹配回文

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

示例： https ://regex101.com/r/xvZ1H0/1

于 2021-10-14T19:06:37.143 回答