Разборы · ЕГЭ, задание 24

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

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

В файле одна очень длинная строка (миллионы символов). Нужно найти длину самой длинной непрерывной подстроки с заданным свойством: без повторяющихся соседей, из определённых символов, являющейся корректным выражением и т. п. 1 балл.

Что нужно знать

• Решение должно быть линейным: одним проходом по строке. Перебор всех подстрок на 10 миллионах символов не закончится.
• Типовой приём — счётчик текущей длины: продолжаем, если символ подходит, иначе начинаем заново.
• Модуль re: re.finditer(шаблон, s) находит все непересекающиеся совпадения; жадные квантификаторы * и + берут как можно больше символов.

Как решать

1. Прочитайте файл целиком: s = open("24.txt").read().strip().
2. Опишите искомую подстроку словами, а затем — шаблоном или условием продолжения цепочки.
3. Проверьте решение на маленьких строках, придуманных вручную, — особенно на «граничных» случаях.

Пример приёма со счётчиком — самая длинная подстрока, в которой соседние символы различны:

s = open("24.txt").read().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)

Пример из демоверсии 2027

Файл состоит из цифр 0, 6, 7, 8, 9 и знаков «–» и «*». Найдите наибольшую длину непрерывной подстроки, которая является корректным арифметическим выражением с неотрицательными целыми числами: два знака не стоят рядом, в числах нет ведущих нулей, число 0 не имеет знака.

Решение. Корректное выражение — это «число, знак, число, …, число». Число — либо одиночный 0, либо цифры, начинающиеся не с нуля: 0|[1-9][0-9]*. Выражение — число, за которым сколько угодно раз идут «знак + число». Ищем все совпадения шаблона и берём самое длинное.

import re

s = open("24.txt").read().strip()
num = r"(?:0|[1-9][0-9]*)"
pattern = num + r"(?:[-*]" + num + r")*"
print(max(len(m.group()) for m in re.finditer(pattern, s)))

Для файла демоверсии ответ — 154.

Почему это работает: из каждой позиции шаблон забирает самое длинное выражение, а следующий поиск начинается сразу после найденного. Более длинное выражение не может начинаться внутри уже найденного — оно упёрлось бы в то же место, где закончилось найденное.

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

• Забывают strip() и считают символ перевода строки частью данных.
• Не учитывают, что «0» — корректное число, а «07» — нет.
• Пишут перебор всех подстрок — на большом файле программа работает часами.
• Проверяют решение только на файле: придумайте 3–4 короткие строки, где ответ очевиден.

Потренироваться: задание 24 новые варианты с проверкой ответа