代码之家 › 专栏 › 技术社区 › polygenelubricants

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

nested-reference palindrome pcre regex php

19

polygenelubricants · 技术社区 · 14 年前

_{这个问题是一个教育性的演示,说明如何在PCRE模式中使用lookahead、嵌套引用和条件句来匹配所有回文,包括那些不能与PCRE手册页中给出的递归模式匹配的回文。}

在PHP代码段中检查此PCRE模式:

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


/';

这个模式似乎可以检测回文,就像在这个测试用例中看到的那样( see also on 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);  
}

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

笔记

此模式使用 nested reference ,这是在 How does this Java regex detect palindromes? ,但与Java模式不同的是,它没有lookbehind(但它确实使用了 conditional ).

另外,请注意PCRE man page 提供递归模式以匹配某些回文:

# 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 ⁿ - 1 times? 和 also on ideone.com

1 回复 | 直到 7 年前

1

28

kennytm 14 年前

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

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

在一种情况下,只有一个字符。这又是由于

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