ЕГЭ по информатике 2026, задание 24: обработка строки

Задание 24 — высокий уровень, 1 балл. Нужна программа примерно на 10–20 строк: обработать символьную строку из файла. Частичного балла нет.

Файл 2026 — `.txt`. Строка может быть длиной в сотни тысяч символов и больше. Квадратичный перебор подстрок не успеет. Нужен один проход.

ФИПИ описывает это как простейший конечный автомат с сумматором. Ошибка — не рассмотреть все пары «текущее состояние и встреченная буква».

Конспект

Типовые вопросы:

• длина самой длинной цепочки из одинаковых символов;
• длина самой длинной подстроки, в которой не больше K вхождений символа;
• сколько раз встречается шаблон, возможно с перекрытием;
• цепочка, удовлетворяющая правилу чередования.

Автомат: вы идёте по строке и храните несколько чисел. Для цепочки одинаковых символов достаточно предыдущего символа и текущей длины. Для «не больше одной буквы A» — число A в текущем окне и левый край окна.

Два указателя, если окно сжимается слева. Левый двигается только вправо, каждый символ обрабатывается ограниченное число раз. Это по-прежнему один проход по смыслу линейного времени.

Перекрытие: в строке AAA подстрока AA встречается дважды, если перекрытия разрешены, и один раз, если ищут непересекающиеся. Условие это задаёт.

Файл может содержать перевод строки. Обычно это одна строка, но иногда несколько. Прочитайте, анализируют каждый ряд отдельно или весь текст. strip() не должен съесть значимые символы, если пробел входит в алфавит.

Шаблон на Python

Самая длинная подстрока, в которой символ X встречается не больше K раз. Замените условие на своё.

s = open("24.txt", encoding="utf-8").read().strip()
X = "A"
K = 2

left = 0
count_x = 0
best = 0
for right, ch in enumerate(s):
    if ch == X:
        count_x += 1
    while count_x > K and left <= right:
        if s[left] == X:
            count_x -= 1
        left += 1
    best = max(best, right - left + 1)
print(best)

Для подряд идущих одинаковых символов автомат короче: переменные prev, cur, best. Для шаблона фиксированной длины можно идти окном s[i:i+len], если длина файла до миллиона, это ещё допустимо. Для правил с памятью не сравнивайте срез на каждом шаге, обновляйте состояние.

Проверьте шаблон на короткой строке, ответ которой посчитали руками, и только потом запускайте на файле. Файл A в этом задании обычно один.

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

• Не разобрана буква, которая сбрасывает автомат.
• Окно сдвинули на 1, хотя нужно было выкинуть символы, пока условие ложно.
• Перекрытия посчитаны или отброшены не по условию.
• Пробел и перевод строки вошли в цепочку.