🔍 Задача 24 ЕГЭ: как регулярные выражения находят подстроки за секунды

Задача №24 ЕГЭ по информатике — одна из самых разнообразных.
Она может быть про:

• поиск максимальной длины подстроки,
• подсчёт количества вхождений шаблона,
• анализ последовательностей символов или цифр.

Из-за этого многие ученики теряются: «Как вообще к этому подступиться?»

Но есть мощный инструмент, который решает целый класс таких задач почти автоматически — регулярные выражения

📌 Часть 1. Что такое регулярные выражения?

Регулярное выражение — это шаблон, по которому можно искать подстроки в тексте.

Представьте, что у вас есть огромный файл с миллионом символов: AABBCAACCC...
Вам нужно найти самую длинную цепочку, состоящую только из букв A, B и C.

Можно перебирать вручную — но это долго.
А можно написать шаблон: [ABC]+ — и заставить программу саму найти все такие участки.

💡 [ABC]+ означает: «одна или более букв из набора A, B, C».

Это и есть регулярное выражение.

📌 Часть 2. Основные обозначения (синтаксис регулярных выражений)

Все задачи ЕГЭ используют ограниченный набор конструкций. Вот что вам нужно знать:

1. [ABC] — набор допустимых символов

• [ABC] — любая одна буква: A, B или C.
• [XYZ] — X, Y или Z.
• [123] — цифра 1, 2 или 3.
• [BCD] — B, C или D.

⚠️ Внутри квадратных скобок нет разделителей — просто подряд символы.

2. + — «один или более раз»

• [ABC]+ — цепочка из одной или более букв A/B/C.
• [XY]+ — цепочка из X и Y, например: X, Y, XXY, YXYX и т.д.

💡 Это ключевая конструкция для поиска максимальных непрерывных подстрок.

3. | — «или»

• (AA|CC)+ — цепочка, состоящая из пар AA или CC, например: AA, CC, AACC, CCAA, AACCAC — нет!
  → Только полные пары: AA, CC, AACC, CCAA, AACCAC — недопустимо, потому что AC — не пара.

⚠️ Без скобок | работает иначе. Поэтому всегда пишите: (AA|CC).

4. (?=(...)) — просмотр вперёд (lookahead)

Это продвинутая конструкция, которая позволяет находить перекрывающиеся подстроки.

Пример:
В строке AAAA нужно найти все пары AA.

• Обычный поиск найдёт: AA (позиции 0–1), потом AA (позиции 2–3) → всего 2.
• Но на самом деле есть 3 пары: (0–1), (1–2), (2–3).

Чтобы найти все, даже перекрывающиеся, используется:

r'(?=(AA))'

• (?=...) — «посмотри вперёд, но не двигайся»,
• AA — то, что ищем,
• Всё выражение — «найди каждую позицию, после которой идёт AA».

💡 Это обязательно в задачах, где просят «максимальное количество непересекающихся пар» — но на самом деле в ЕГЭ часто имеют в виду перекрывающиеся, и тогда нужен lookahead.

5. \d и [0-9] — цифры

• [0-9] — любая цифра от 0 до 9.
• То же самое, что \d, но в ЕГЭ чаще используют [0-9].

6. [1-9] — цифры от 1 до 9 (без нуля)

Важно! В задачах про числа нуль в начале запрещён, поэтому:

• [1-9][0-9]* — натуральное число без ведущих нулей.

Справочник обозначений

Фигурные скобки { }

• Не путайте с [ ]!
• { } — только квантификаторы, они не задают набор символов.
• Пример: A{2} — две буквы A,
  A{2,5} — от двух до пяти A.

Круглые скобки ( )

• Используются для:Группировки: (AB)+,
  Захвата подстрок: re.search(r'(A)(B)', s) → group(1) = 'A', group(2) = 'B',
  Вложенных условий: (AA|CC)+.
  

⚠️ Важно: если в шаблоне есть скобки, а вы используете finditer, то match.group(1) — первая захваченная группа, match.group() — вся подстрока.

Знак ^

• ^ в начале шаблона — начало строки (anchor).
• Пример: ^A — найдёт "A" только в начале строки.
• Внутри [...] — инверсия: [^ABC] — любой символ, кроме A, B, C.

Пробелы

• Пробел — это символ!
  Если в строке есть пробел, а в шаблоне его нет — совпадения не будет.
• Чтобы найти пробел, пишите явно: (пробел) или \s.
• В ЕГЭ строки без пробелов (только буквы и цифры), поэтому пробелы в шаблонах не используются.

Экранирование: \

• Некоторые символы имеют специальное значение: ., *, +, ?, (, ), [, ], {, }, ^, $, \.
• Чтобы использовать их как обычные символы — экранируйте обратным слешом:\. — точка как символ,
  \* — звёздочка как символ,
  \( — открывающая скобка как символ.
  

💡 В задачах ЕГЭ часто встречаются знаки -, *, + — их нужно экранировать, если они входят в шаблон как литералы.
Но в большинстве задач они используются как операторы — тогда экранирование не нужно.

Запись на занятия здесь: https://t.me/nka39

📌 Часть 3. Решение задач

✅ Задача 1

Условие:
В файле строка из букв A, B, C, D, E.
Найти длину самой длинной подстроки, состоящей только из A, B, C (в любом порядке).

Решение

Пошаговое объяснение:

1. from re import * — подключаем все функции модуля re.
2. s = open('24-1.txt').readline() — читаем одну строку из файла.
3. reg = r'[ABC]+' — шаблон: «цепочка из A, B или C, длиной ≥1».
4. finditer(reg, s) — находит все такие цепочки.
5. [x.group() for x in ...] — извлекает сами подстроки (например, 'ABBC', 'AAC').
6. max(..., key=len) — выбирает самую длинную.
7. print(len(m)) — выводит её длину.

✅ Это базовый шаблон для всех задач на «максимальную подстроку из заданных символов».

✅ Задача 2

Условие:
Строка из X, Y, Z. Найти максимальное количество пар ZX или ZY.

Объяснение:

• (ZX|ZY)+ — цепочка из полных пар: ZX, ZY, ZXZY, ZYZX и т.д.
• len(x.group()) — длина всей цепочки (в символах).
• // 2 — переводим в количество пар (каждая пара — 2 символа).
• max(...) — находим максимальное количество пар в одной цепочке.

💡 Здесь не используются перекрытия, потому что пары идут подряд без пропусков.

✅ Задача 3

Условие:
Буквы: A (гласная), B/C/D (согласные).
Найти максимальное количество пар «согласная + гласная».

Решение:

Объяснение:

• [BCD] — согласная,
• [A] — гласная,
• ([BCD][A])+ — цепочка из пар: BA, CA, DA, BACA и т.д.
• Делим длину на 2 → получаем число пар.

✅ Задача 4

Текстовый файл содержит строку из заглавных латинских букв А, В и С,
всего не более чем из 106 символов. Найдите максимальное количество подряд идущих пар символов АА или СС. Искомая подстрока может включать только пары АА, только пары СС или содержать одновременно как пары АА, так и пары СС.

Решение:

Объяснение:

1. Сначала создаём базовый шаблон: reg = r'(AA|CC)+'.
2. Затем оборачиваем его в lookahead:

reg = rf'(?=({reg}))'

1. → Это даёт: r'(?=((AA|CC)+))'.
2. Теперь finditer находит каждую позицию, где начинается такая цепочка — даже если она перекрывается.
3. x.group(1) — первая группа в скобках, т.е. сама цепочка (например, 'AAAA').
4. len(...) // 2 — количество пар.

💡 Без (?=...) вы пропустите перекрывающиеся случаи.
Например, в 'AAAA' без lookahead найдётся только 'AAAA' → 2 пары.
А с lookahead — будут рассмотрены и 'AAAA' (начиная с 0), и 'AAA' (с 1), и 'AA' (с 2) → максимум 2, но в других случаях разница критична.

✅ Задача 5

Текстовый файл содержит строку из символов А, В, С и цифр 1, 2, 3,
всего не более чем 105 символов. Определите максимальное количество идущих подряд пар символов вида «буква + цифра».

Объяснение:

• [ABC] — буква,
• [123] — цифра,
• ([ABC][123])+ — цепочка пар: A1, B2, C3A1 и т.д.
• Используем lookahead, чтобы учесть все возможные начала цепочек.

✅ Задача 6

Объяснение:

• Порядок в (YZZ|XY|YZ) важен: сначала более длинные (YZZ), потом короткие.
• Иначе YZ может «съесть» начало YZZ, и шаблон не совпадёт.
• lookahead — чтобы найти все возможные подстроки, даже перекрывающиеся.
• Здесь не делим на 2, потому что просят длину подстроки, а не количество блоков.

✅ Задача 7

Текстовый файл cостоит не более чем из 105 символов и содержит
только символы, обозначающие знаки «-», «*», и цифры 0, 7, 8, 9. Определите в прилагаемом файле максимальное количество идущих подряд символов, которые образуют математически правильную последовательность, в которую входят знаки «-» или «*» и натуральные числа без незначащих нулей.

Объяснение:

1. nat = r'([1-9][0-9]*)' — натуральное число без ведущего нуля:[1-9] — первая цифра от 1 до 9,
   [0-9]* — затем любые цифры (включая ноль), ноль или более раз.
   
2. posl = rf'{nat}([-*]{nat})+' — выражение:сначала одно число,
   затем один или более раз: (знак + число).
   
3. Пример корректного: 708-897*8700.
4. finditer находит все такие выражения.
5. max(..., key=len) — самое длинное.

💡 Здесь не нужен lookahead, потому что выражения не перекрываются — они чётко разделены.

✅ Задача 8

Текстовый файл состоит не более чем из 105 символов и содержит только цифры шестнадцатеричной системы счисления и знаки арифметических операций «+» и «*». Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами, записанными в шестнадцатеричной системе счисления. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число 0 не имеет знака.

Объяснение:

• num = r'([1-9A-F][0-9A-F]*|0)' — число в 16-СС:либо 0,
  либо от 1 до F, затем любые цифры/буквы.
• posl = ... ([+*]{num})* — после первого числа может идти ноль или более операций.
• * вместо +, потому что выражение может быть одним числом.

✅ Задача 9

Текстовый файл состоит не более чем из 105 символов и содержит
только десятичные цифры, а также знаки «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами (без знака), значение которого равно нулю. В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел
отсутствуют незначащие (ведущие) нули. В ответе укажите количество символов в найденном выражении.

Объяснение:

• Чтобы выражение равнялось нулю, достаточно одного нуля в произведении.
• proiz = ...0... — произведение, содержащее 0.
• summa = proiz (+ proiz)* — сумма таких произведений.
• Используется lookahead, чтобы найти все возможные выражения, даже вложенные.
• max(..., key=len) — количество символов в самой длинной строке.
  

📌 Часть 5. Почему это работает? Глубокий взгляд

Регулярные выражения — это конечные автоматы под капотом.
Когда вы пишете [ABC]+, Python строит автомат, который:

1. Начинает в состоянии «ожидание A/B/C»,
2. При чтении A/B/C — остаётся в том же состоянии,
3. При другом символе — завершает совпадение.

Это позволяет обрабатывать миллионы символов за доли секунды.

А конструкция (?=...) — это нулевая ширина: она проверяет условие, но не потребляет символы, поэтому поиск продолжается с той же позиции — отсюда и перекрытия.

📌 Часть 6. Ограничения и ловушки

1. Порядок в | важен
   В (YZZ|YZ) сначала проверяется YZZ. Если написать (YZ|YZZ), то YZ совпадёт раньше, и YZZ не будет найдено.
2. Lookahead замедляет код
   Но на ЕГЭ объём данных небольшой — это не проблема.
3. Не все задачи 24 решаются через регулярки
   

📌 Заключение

Регулярные выражения — это мощный, но специализированный инструмент.
Они идеально подходят для задач, где нужно:

• найти непрерывную подстроку по шаблону,
• подсчитать количество блоков,
• учесть перекрытия.

Все задачи решаются однотипно:

1. Составить шаблон,
2. Найти все совпадения,
3. Выбрать нужное (макс/мин/сумма).

Но помните: это только один тип задачи 24.

Есть и другие прототипы:

• динамическое программирование на строках,
• ручной перебор с условиями
• задачи на 2 указателя
• задачи на разбиение строки.

О них — в следующих статьях.

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

Подпишитесь на канал и научитесь решать все задания ЕГЭ по информатике!

Удачи на экзамене!

Записаться ко мне на занятия можно тут https://t.me/nka39