Что нужно знать о шаблонах

В задании 24 почти всегда ищут цепочку символов с каким-то свойством. Регулярное выражение описывает такую цепочку шаблоном. Функция re.findall из стандартного модуля re возвращает все куски строки, подходящие под шаблон: слева направо и без пересечений. Остаётся взять самый длинный кусок или посчитать их.

Для задания 24 хватает нескольких элементов шаблона:

  • [ABC] — один символ из перечисленных;
  • [^ABC] — один любой символ, кроме перечисленных;
  • + — предыдущий элемент один или больше раз подряд, * — ноль или больше раз, ? — ноль или один раз;
  • (?:...) — группа, к которой можно применить +, * или ?;
  • | — или: подходит левая часть шаблона или правая;
  • (?=...) — проверка «дальше стоит ...», которая не забирает символы.

Шаблон записывают строкой с буквой r перед кавычкой: r'[^GWP]+'. Так Python не трогает обратную косую черту, если она встретится в шаблоне.

Статья о Python. В C++ до GCC 16 те же шаблоны на файле задания 24 часто роняют программу: std::regex не справляется с длинным совпадением. Почему там лучше решать циклом, рассказано в отдельной статье «Регулярные выражения в задании 24 на C++».

Самая длинная цепочка без запрещённых букв

Найдём самую длинную подстроку, в которой нет букв G, W и P. Шаблон [^GWP]+ описывает разрешённые символы, идущие подряд. Каждый найденный кусок тянется до ближайшей запрещённой буквы, поэтому среди них есть и самый длинный.

Python 3
import re

s = input()
# [^GWP]+ — одна или больше букв подряд, среди которых нет G, W и P.
# findall возвращает все такие куски слева направо; каждый тянется
# до ближайшей запрещённой буквы, поэтому самая длинная серия не обрезается.
parts = re.findall(r'[^GWP]+', s)
print(max(len(p) for p in parts))

В условии гарантировано, что такая цепочка есть. Без этой гарантии findall может вернуть пустой список, и max завершится ошибкой. Тогда пишут max((len(p) for p in parts), default=0).

Чередование букв и цифр

Строка состоит из букв Q, R, W и цифр 1, 2, 4. Нужна самая длинная цепочка, в которой буквы и цифры чередуются. Цепочка начинается с буквы или с цифры. С буквы она продолжается парами «цифра, буква», с цифры — парами «буква, цифра», а в конце может остаться один символ другого типа. Два варианта начала соединяются знаком |.

Python 3
import re

s = input()
letter, digit = '[QRW]', '[124]'
# Цепочка с буквы: буква, затем пары «цифра, буква», в конце может стоять цифра.
# Цепочка с цифры — то же с обменом ролей. Один символ тоже подходит.
# (?:...) — группа без захвата: с обычными скобками findall вернул бы
# содержимое скобок, а не всё совпадение.
pattern = (letter + '(?:' + digit + letter + ')*' + digit + '?'
           + '|' + digit + '(?:' + letter + digit + ')*' + letter + '?')
print(max(len(p) for p in re.findall(pattern, s)))

Шаблон вышел длиннее решения обычным циклом. При сложном условии регулярное выражение легко написать неверно, поэтому сначала проверьте его на примерах из условия и только потом запускайте на файле.

Вхождения с пересечениями

Нужно посчитать, сколько раз в строке встречается ABABA, включая пересекающиеся вхождения. Ни findall с шаблоном ABABA, ни метод count с этим не справятся: после совпадения поиск продолжается с его конца. В строке ABABABA они найдут одно вхождение, хотя их два.

Шаблон (?=ABABA) только проверяет, что с текущей позиции начинается ABABA, и не забирает символы. Следующий поиск начинается со следующей позиции, и пересекающиеся вхождения тоже находятся. Каждое совпадение — пустая строка, поэтому считают их количество.

Python 3
import re

s = input()
# (?=ABABA) — проверка «отсюда начинается ABABA», которая не забирает символы.
# Поэтому следующий поиск идёт со следующей позиции и находит пересекающиеся вхождения.
# s.count('ABABA') их пропускает: в ABABABA он насчитает одно вхождение вместо двух.
print(len(re.findall(r'(?=ABABA)', s)))

Когда регулярные выражения не помогают

Если условие считает символы внутри фрагмента — «не менее 270 букв Z», «ровно 80 букв Y», — шаблон не подходит. Описать такой фрагмент шаблоном можно, но findall проверяет не все возможные начала, а только идущие после предыдущего совпадения, и самый короткий или самый длинный фрагмент может пропустить. Такие задачи решают скользящим окном: две границы, которые двигаются по строке.

Типичные ошибки

  • Скобки без ?:. Если в шаблоне есть обычные скобки, findall возвращает их содержимое, а не всё совпадение. Для группировки пишите (?:...).
  • * вместо +. Шаблон [^GWP]* совпадает и с пустой строкой, поэтому в списке появятся пустые куски, и подсчёт цепочек даст неверный ответ.
  • Точка в шаблоне. Символ . означает любой символ. Саму точку записывают как [.].
  • Перевод строки из файла. Если прочитать строку из файла без strip(), в её конце останется перевод строки. Шаблон [^GWP]+ примет его за разрешённый символ, и ответ может вырасти на единицу.