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

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

19 голосов
/ 19 сентября 2010

Этот вопрос является образовательной демонстрацией использования прогнозной, вложенной ссылки и условных выражений в шаблоне 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 предупреждает, что этот рекурсивный шаблон НЕ МОЖЕТ обнаружить все палиндромы (см .: Почему это рекурсивное регулярное выражение совпадает только тогда, когда символ повторяется 2 n - 1 раз? и также на ideone.com ), но вложенный шаблон ссылки / положительного прогнозирования, представленный в этом вопросе, может.

1 Ответ

25 голосов
/ 20 сентября 2010

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

^(.)(.)(.) ... \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 совпадений ничего. Итак 

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