Задание 24 ЕГЭ по информатике: обработка символьных строк — разбор и примеры

В задании 24 дан текстовый файл с одной очень длинной строкой — обычно до миллиона символов из нескольких заглавных латинских букв (иногда с цифрами и знаками). Нужно найти характеристику подстроки, удовлетворяющей условию: чаще всего длину самой длинной подстроки определённого вида. Вручную такой файл не обработать, поэтому задание проверяет умение написать короткую и, главное, быструю программу. Переборное решение «все начала × все концы» на строке длиной 10⁶ не успеет за время экзамена.

Что проверяет задание

• чтение данных из файла и работу со строками в Python;
• понимание терминов: подстрока — непрерывный фрагмент строки (в отличие от подпоследовательности), длина — число символов в ней;
• умение выбрать линейный алгоритм: один проход со счётчиком или метод двух указателей (скользящее окно);
• внимательность к граничным случаям: подстрока в самом конце файла, пустой ответ.

Типичные формулировки

1. Самая длинная подстрока, в которой нет двух одинаковых соседних символов.
2. Самая длинная подстрока, содержащая не более k букв заданного вида (например, не более двух букв D).
3. Самая длинная подстрока, состоящая из повторяющейся «пары» или «тройки» символов.
4. Самая длинная подстрока, которая начинается и заканчивается определённой буквой и не содержит внутри другой буквы.
5. Подсчёт: сколько раз встречается комбинация, какой символ чаще всего стоит после заданного.

Первые два типа покрывают большую часть вариантов: условие либо «локальное» (касается соседних символов), либо «счётное» (ограничивает количество чего-то в подстроке).

Пошаговый метод

1. Определите тип условия. Если оно проверяется по соседним символам — подойдёт один проход с текущей длиной. Если ограничено число символов в подстроке — нужен метод двух указателей.
2. Один проход: идём по строке и храним длину текущего подходящего участка cur. Если очередной символ продолжает участок — увеличиваем cur, иначе начинаем новый участок. После каждого шага обновляем максимум.
3. Два указателя: правая граница right идёт по строке, левая left сдвигается только вперёд, когда окно перестаёт удовлетворять условию. Каждый символ входит в окно и выходит из него не больше одного раза — получаем линейное время.
4. Проверьте программу на маленькой строке, ответ для которой знаете (например, из условия или придуманной вами), и только потом запускайте на файле.

Разбор примера

Пусть «файл» содержит строку из 28 символов (на экзамене она будет в тысячи раз длиннее, но алгоритм тот же):

CABBCADCBDACDBDCABBADCBACDDA

Вопрос 1. Найдите длину самой длинной подстроки, в которой никакие два соседних символа не совпадают.

Строка «рвётся» там, где стоят два одинаковых соседних символа: BB на позициях 3–4, BB на позициях 18–19 и DD на позициях 26–27. Значит, подходящие участки: позиции 1–3 (длина 3), 4–18 (длина 15), 19–26 (длина 8), 27–28 (длина 2). Самая длинная подстрока — BCADCBDACDBDCAB.

Ответ: 15.

Вопрос 2. Найдите длину самой длинной подстроки, содержащей не более двух букв D.

Буквы D стоят на позициях 7, 10, 13, 15, 21, 26, 27. Подстрока с не более чем двумя D не может включать три из них подряд по номерам. Например, окно между D на позиции 13 (не включая её) и началом строки — это позиции 1–12 с буквами D на 7 и 10, длина 12. Окно между D на позиции 13 и D на позиции 26 (не включая их) — позиции 14–25, в нём D на 15 и 21, длина тоже 12. Остальные окна короче.

Ответ: 12.

Код на Python

Шаблон для вопроса 1 (один проход):

s = open('24.txt').readline().strip()

best = cur = 1
for i in range(1, len(s)):
    if s[i] != s[i - 1]:
        cur += 1
    else:
        cur = 1
    best = max(best, cur)
print(best)                     # 15 для строки из примера

Шаблон для вопроса 2 (два указателя):

s = open('24.txt').readline().strip()

left = cnt = best = 0
for right, ch in enumerate(s):
    if ch == 'D':
        cnt += 1
    while cnt > 2:              # окно стало «плохим» — сдвигаем левую границу
        if s[left] == 'D':
            cnt -= 1
        left += 1
    best = max(best, right - left + 1)
print(best)                     # 12 для строки из примера

Для «счётных» условий есть и альтернативный приём: найти позиции всех нужных букв и рассмотреть окна между позициями с номерами i и i + k + 1. Он быстрый, но в нём легко ошибиться на краях строки, поэтому метод двух указателей надёжнее.

Как выбрать алгоритм для нового условия

Перед тем как писать код, задайте себе вопрос: если подстрока удовлетворяет условию, будет ли удовлетворять ему любая её часть? Для условий «не более двух букв D» и «нет одинаковых соседей» ответ — да, и тогда работает скользящее окно: расширяем окно вправо, а при нарушении условия сжимаем слева. Если же условие требует чего-то обязательно (например, «ровно три буквы D» или «начинается с A и заканчивается на B»), часть подходящей подстроки может уже не подходить. Тогда помогает приём с позициями: запишите индексы нужных символов в список и рассматривайте окна между ними. Такая подготовка занимает минуту и спасает от долгой отладки.

Частые ошибки

• Перебор всех подстрок. Двойной цикл с вызовом count для каждой подстроки работает за время, пропорциональное квадрату или кубу длины, и на файле не завершится.
• Забывают последний участок. Если максимум обновлять только при «разрыве», участок в конце строки не будет учтён. Обновляйте максимум на каждом шаге.
• Неверное начальное значение. Для строки длиной 1 ответ на вопрос 1 равен 1, а не 0.
• Лишний символ перевода строки. Без strip() в конце строки остаётся символ \n, и он может «удлинить» подстроку.
• Путают подстроку и подпоследовательность. Подстрока — только подряд идущие символы.
• Читают файл не тот или не целиком. Проверьте длину строки командой print(len(s)) — она должна совпадать с ожиданием.

Потренируйтесь

Решите задания № 24 в банке и обязательно попробуйте задачи с проверкой кода: там программа проверяется автотестами на больших строках, и переборное решение не уложится в лимит времени. Следующее задание — задание 25: делители и маски чисел.