Как этот шаблон PCRE обнаруживает палиндромы?

Этот вопрос является образовательной демонстрацией использования lookahead, вложенной ссылки и условных выражений в шаблоне PCRE для соответствия всем палиндромам, включая те, которые не могут быть сопоставлены рекурсивным шаблоном, данным в человеке PCRE стр.суб >

Изучите этот шаблон PCRE в PHP-фрагменте:

$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 нет lookbehind (но он использует conditional).

Кроме того, обратите внимание, что страница PCRE представляет собой рекурсивный шаблон для соответствия некоторым палиндромам:

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

Страница man предупреждает, что этот рекурсивный шаблон НЕ может обнаружить все палиндромы (см. Почему это рекурсивное регулярное выражение будет соответствовать только тогда, когда символ повторяет 2 n - 1 раз? и также на ideone.com), но вложенный шаблон/позитивный шаблон обзора, представленный в этом вопросе, может.

Ответы

Ответ 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-й половиной.

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

Это работает хорошо, за исключением одного случая - когда есть только 1 символ. Это опять же из-за \2 ничего не соответствует. Итак,

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