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

Этот вопрос является образовательной демонстрацией использования прогнозных данных, вложенных ссылок и условных выражений в шаблоне 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|.))$

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

Источник

2 ответа

Решение

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

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

Теперь это соответствует первой половине палиндрома. Как насчет второй половины? Ну, после того, как 1-я половина соответствует, записанный захват \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.
Источник

Я хочу предложить свое собственное решение. Это регулярное выражение, которое я написал некоторое время назад для решения сопоставления палиндромов с помощью PCRE / PCRE2.

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

Пример:https://regex101.com/r/xvZ1H0/1

Источник
Другие вопросы по тегам