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

Question

Как этот шаблон 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, здесь нет поиска (но он использует условное ).

Также обратите внимание, что на справочной странице PCRE представлен рекурсивный шаблон, соответствующий некоторым палиндромам:

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

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

18

php regex pcre palindrome nested-reference

Author: Community, 2010-09-19

Source

1 answers

score 24 · Accepted Answer

Давайте попробуем понять регулярное выражение, построив его. Во-первых, палиндром должен начинаться и заканчиваться одной и той же последовательностью символов в противоположном направлении:

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

Мы хотим переписать это так, чтобы за ... следовала только конечная длина шаблонов, чтобы мы могли преобразовать ее в *. Это возможно с помощью lookahead:

^(.)(?=.*\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-ю половину. Так что давайте просто поставим на этом точку.

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