Этот вопрос является образовательной демонстрацией использования 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 (но он использует условный ).
Также обратите внимание, что на странице руководства PCRE представлен рекурсивный шаблон, соответствующий нескольким палиндромам:
# the recursive pattern to detect some palindromes from PCRE man page ^(?:((.)(?1)\2|)|((.)(?3)\4|.))$
Страница man предупреждает, что этот рекурсивный шаблон НЕ может обнаружить все палиндромы (см.: Почему это рекурсивное регулярное выражение будет соответствовать только тогда, когда символ повторяется 2 n – 1 раз? И также на ideone.com ), но представлен вложенный шаблон reference / positive lookahead в этом вопросе можно.
Попробуем понять регулярное выражение, построив его. Во-первых, палиндром должен начинаться и заканчиваться той же последовательностью символов в противоположном направлении:
^(.)(.)(.) ... \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.