Каталог: Задание №24. Анализ символьных строк (до 5 000 000 символов)

Банк задач: 316 Формат ЕГЭ 2026 Повышенный / Высокий (1 балл) 5-10 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №24

Тема кодификатора Поиск максимальных цепочек, метод маркеров и сплитов, линейная динамика и скользящее окно

Сложность и баллы Повышенный / Высокий (1 балл)

Рекомендуемое время 5-10 мин

Инструменты решения Python 3, open('24.txt'), replace() + split(), Метод сплитов по символу, Однопроходная динамика O(N)

В текстовом файле записана гигантская строка (до 5 000 000 знаков). Задача — найти максимальную длину непрерывной подстроки, удовлетворяющей условию: цепочки пар (Согласная+Гласная), не более K определенных символов, чередующиеся последовательности или арифметические выражения.

Основные прототипы и разновидности

Тип 1: Метод маркеров и сплитов replace() + split()

Замена целевых пар/троек на маркер '*' с последующей заменой остальных букв на пробелы и вычислением max(len(chunk) for chunk in s.split()).

Тип 2: Не более K вхождений определенного символа (Хит ЕГЭ)

Сплит по ключевой букве parts = s.split('A') и суммирование длин соседних K+1 блоков плюс K.

Тип 3: Чередующиеся символы и однопроходная динамика O(N)

Подстроки, где никакие две гласные или две согласные не стоят рядом. Линейный проход со счетчиком cur_len.

Тип 4: Арифметические выражения и валидные цепочки

Поиск корректных выражений вида '12+45*3' без ведущих нулей и подряд идущих знаков операций.

Теоретический фундамент и алгоритмы

1. Метод 1: Маркеры и сплиты (для цепочек пар / троек):

Если требуется найти самую длинную цепочку пар вида Согласная + Гласная (например, из букв C, D, F и A, O):

Заменяем все валидные пары на звёздочку *:
```
for c in 'CDF':
    for v in 'AO':
        s = s.replace(c + v, '*')
```
Все остальные оставшиеся символы заменяем на пробелы:
```
for ch in 'CDFAO':
    s = s.replace(ch, ' ')
```
Разбиваем по пробелам и берем максимум: max_len = max(len(chunk) for chunk in s.split()).

2. Метод 2: Сплиты по целевому символу (Не более $K$ букв 'T'):

Окно, содержащее ровно $K$ букв 'T', состоит ровно из $K+1$ соседних фрагментов массива s.split('T') плюс сами $K$ букв 'T':

parts = s.split('T')
max_len = 0
for i in range(len(parts) - K):
    # Суммируем длины K+1 кусков и добавляем K разделителей 'T':
    current_window = sum(len(parts[j]) for j in range(i, i + K + 1)) + K
    max_len = max(max_len, current_window)

3. Метод 3: Универсальная однопроходная динамика $O(N)$:

cur_len = 1
max_len = 1
for i in range(1, len(s)):
    if (s[i] in vowels) != (s[i-1] in vowels): # Чередование
        cur_len += 1
        max_len = max(max_len, cur_len)
    else:
        cur_len = 1

Лайфхаки и фишки для ускорения

Совет

Метод s.split('T') работает мгновенно (за 0.05 секунды) даже на 5-мегабайтных файлах!

Совет

Для подсчета длины в парах умножайте на 2 только если в задаче спрашивают количество символов, а не пар.

Частые ошибки и экзаменационные ловушки

Ошибка: Вложенные циклы s[i:j] с квадратичной сложностью O(N^2)
Строка из 2 000 000 символов потребует 4 триллиона операций и зависнет намертво!

Правильно: Использовать строго линейные алгоритмы O(N) (метод сплитов или 1 цикл).

Ошибка: replace('CA', '*') без замены остальных букв на пробелы
Если буквы останутся в строке, len(chunk) посчитает их вместе со звёздочками!

Правильно: Все символы алфавита, не превратившиеся в '*', заменять на пробелы.

ГРОБ №24: Цепочка пар, начинающаяся или заканчивающаяся одиночным символом

В вопросе задачи: 'максимальная длина в символах'. Цепочка может иметь вид (Гласная + пары + Согласная).

Алгоритм решения: После нахождения максимальной цепочки звёздочек проверьте соседние символы слева и справа от найденного блока в исходной строке.

Практические задачи из банка КИМ (Всего: 316)

Решать в песочнице СмартКИМ

Задача #9005 №24 ЕГЭ