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

Подтемы

Задания для подготовки
77 задач

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

Задание 24 проверяет умение анализировать большие текстовые файлы, состоящие из ограниченного набора символов (обычно это буквы X, Y, Z или цифры), и находить в них подстроки с заданными свойствами. Речь идёт не о ручном анализе — файл содержит до $10^6$ символов, поэтому решение обязательно предполагает написание программы на любом языке программирования (чаще всего Python, Pascal или C++).

Проверяемые навыки:

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

Задание относится к практическому программированию, но по сути является задачей на строки и последовательности — типичная тема для дискретной математики и информатики.

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

Типичная формулировка звучит так: "Текстовый файл состоит не более чем из $10^6$ символов X, Y и Z. Определите [какую-то характеристику] в этом файле". Дальше идёт ссылка на сам файл, который нужно скачать и обработать программой.

Варианты того, что требуется найти:

максимальная длина серии одинаковых символов (например, самая длинная цепочка из X);
максимальная длина серии, где соседние символы различны;
длина максимальной цепочки, повторяющей определённый паттерн (например, XYZXYZ...);
количество вхождений определённой подстроки;
сумма длин серий, удовлетворяющих условию.

Задание оценивается в 2 первичных балла. Для получения полного балла нужно верно найти число — ответ. Частичный балл (1 балл) в этом задании, как правило, не предусмотрен: либо ответ верный, либо нет, поскольку проверяется единственное числовое значение. Ответ записывается в виде целого числа без пробелов и дополнительных символов.

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

Для уверенного решения задания 24 нужно владеть базовыми конструкциями программирования и понимать логику работы с сериями символов.

Понятие серии — это максимальная по длине подстрока, состоящая из символов, удовлетворяющих некоторому условию (все одинаковые, все разные с соседним, повторяют паттерн).
Длина серии — количество символов в серии, обозначим её $L$ .
Счётчик текущей серии — переменная, которая увеличивается на 1 при выполнении условия и сбрасывается в 1 (или 0), когда условие нарушается.
Максимум по ходу чтения: $L_{max} = \max(L_{max}, L_{current})$ — обновляется на каждом шаге или при завершении серии.
Условие смены символа: если текущий символ $s_i$ не равен предыдущему $s_{i-1}$ , то серия чередования продолжается; иначе — обрывается.
Модель циклического паттерна: для цепочки вида XYZXYZ... символ на позиции $i$ (при нумерации с 0) должен совпадать с символом паттерна на позиции $i \bmod k$ , где $k$ — длина паттерна (например, $k=3$ для XYZ).
Работа с файлом: чтение всего файла в строку или посимвольно в цикле, обязательно с учётом больших объёмов данных (до $10^6$ символов) — важно избегать медленных операций (например, конкатенации строк в цикле в некоторых языках).
Инициализация счётчиков: перед первым символом нужно либо задать особые начальные значения, либо обрабатывать первый символ отдельно, чтобы не сравнивать с несуществующим "нулевым" элементом.

Методы решения

Метод 1. Подсчёт серии одинаковых символов

Идея: пройти по строке, сравнивая каждый символ с предыдущим. Если символы совпадают — увеличить счётчик, если нет — сравнить с максимумом и сбросить счётчик.

Мини-пример: строка "XXXYYXXXX". Серии X: длина 3, длина 4. Максимум — 4.

count = 1
max_len = 1
for i in range(1, len(s)):
 if s[i] == s[i-1]:
 count += 1
 else:
 max_len = max(max_len, count)
 count = 1
max_len = max(max_len, count)

Метод 2. Подсчёт серии одинаковых символов конкретного вида (например, только X)

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

Мини-пример: строка "XXYXXXY". Серии X: 2 и 3. Ответ — 3.

count = 0
max_len = 0
for ch in s:
 if ch == 'X':
 count += 1
 max_len = max(max_len, count)
 else:
 count = 0

Метод 3. Подсчёт серии чередующихся символов (соседние различны)

Идея: серия продолжается, пока каждый новый символ отличается от предыдущего. Как только два одинаковых символа встают рядом — серия обрывается и начинается заново.

Мини-пример: строка "XYXYYZXY". Серии: "XYXY" (длина 4), затем "YZXY" (длина 4). Ответ — 4.

count = 1
max_len = 1
for i in range(1, len(s)):
 if s[i] != s[i-1]:
 count += 1
 else:
 count = 1
 max_len = max(max_len, count)

Метод 4. Подсчёт длины цепочки, повторяющей заданный паттерн (например, XYZXYZ...)

Идея: задать паттерн (строку из нескольких символов, например "XYZ") и проверять, совпадает ли символ на позиции $i$ с символом паттерна на позиции $i \bmod k$ , где $k$ — длина паттерна. Если совпадает — серия продолжается, иначе — начинается новая серия, отсчёт внутри паттерна начинается заново с позиции 0.

Мини-пример: паттерн "XYZ", строка "XYZXYXYZZ". Проверяем: X-Y-Z-X-Y (5 символов совпадают с продолжением паттерна), затем встречается X вместо Z — серия обрывается, длина 5. Дальше начинается новый отсчёт.

pattern = "XYZ"
k = len(pattern)
count = 0
max_len = 0
j = 0 # позиция в пределах паттерна
for ch in s:
 if ch == pattern[j % k]:
 count += 1
 j += 1
 else:
 max_len = max(max_len, count)
 # проверяем, не начинается ли новая цепочка с текущего символа
 if ch == pattern[0]:
 count = 1
 j = 1
 else:
 count = 0
 j = 0
max_len = max(max_len, count)

Метод 5. Подсчёт количества серий, удовлетворяющих условию длины

Иногда требуется не максимальная длина, а количество серий длиной не менее заданного значения $N$ или сумма длин таких серий. Логика такая же, как в предыдущих методах, но вместо обновления максимума ведётся подсчёт количества найденных подходящих серий.

Мини-пример: найти количество серий из X длиной не менее 3 в строке "XXXYXXXXY". Первая серия — длина 3 (подходит), вторая — длина 4 (подходит). Ответ — 2.

Алгоритм решения по шагам

Прочитать условие внимательно и выделить: какие символы участвуют, какое условие определяет серию (одинаковые, разные, паттерн), что именно нужно найти (максимум длины, количество, сумму).
Скачать файл и открыть его в режиме чтения текста.
Считать содержимое в строку целиком (если размер файла позволяет, до $10^6$ символов — это допустимо для большинства языков) или организовать построчное/посимвольное чтение.
Инициализировать переменные: счётчик текущей серии (count), переменную максимума (max_len), при необходимости — индекс паттерна (j).
Обработать первый символ отдельно, если это упрощает логику (например, задать count = 1, если первый символ уже удовлетворяет условию).
Организовать цикл по всем символам начиная со второго (или с первого, в зависимости от логики), внутри которого:

проверяется условие продолжения серии;
если условие выполняется — счётчик увеличивается;
если условие нарушается — обновляется максимум, счётчик сбрасывается (с учётом возможного начала новой серии сразу с текущего символа).

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

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

Пример 1

Условие: файл содержит не более $10^6$ символов X, Y, Z. Нужно найти максимальную длину подряд идущих символов, где каждые два соседних различны.

Шаг 1. Формализуем условие: ищем максимальную длину подстроки $s_i, s_{i+1}, \ldots, s_{i+L-1}$ , такую что для любого $j$ из этого диапазона выполняется $s_j \neq s_{j+1}$ .

Шаг 2. Это классический метод 3 (чередование соседних символов).

Шаг 3. Пишем программу:

with open('24.txt') as f:
 s = f.read()
count = 1
max_len = 1
for i in range(1, len(s)):
 if s[i] != s[i-1]:
 count += 1
 else:
 count = 1
 max_len = max(max_len, count)
print(max_len)

Шаг 4. Логика: как только два соседних символа совпадают, цепочка чередования прерывается, и отсчёт новой серии начинается заново с текущего символа (счётчик сбрасывается в 1, а не в 0, так как сам текущий символ уже входит в новую потенциальную серию).

Шаг 5. После обработки всего файла программа выводит значение $L_{max}$ .

Ответ: 35.

Пример 2

Условие: файл содержит не более $10^6$ символов X, Y, Z. Нужно определить длину самой длинной последовательности, состоящей только из символа X (хотя бы один символ X должен присутствовать).

Шаг 1. Здесь важна серия только из одного конкретного символа — это метод 2.

Шаг 2. Условие продолжения серии: текущий символ равен 'X'. Если встречается любой другой символ (Y или Z), серия обрывается, счётчик обнуляется.

Шаг 3. Программа:

with open('24.txt') as f:
 s = f.read()
count = 0
max_len = 0
for ch in s:
 if ch == 'X':
 count += 1
 if count > max_len:
 max_len = count
 else:
 count = 0
print(max_len)

Шаг 4. Важно не забывать, что при встрече символа, отличного от X, счётчик сбрасывается именно в 0, а не в 1, так как этот символ не является частью искомой серии (в отличие от предыдущего примера, где чередование могло продолжиться с текущего символа).

Шаг 5. Максимум обновляется на каждом шаге внутри условия, поэтому дополнительной проверки после цикла не требуется.

Ответ: 19.

Пример 3

Условие: файл содержит не более $10^6$ символов X, Y, Z. Нужно определить максимальную длину цепочки вида XYZXYZXYZ..., составленной из фрагментов "XYZ" (последний фрагмент может быть неполным).

Шаг 1. Это метод 4 — работа с паттерном длиной $k=3$ : "XYZ".

Шаг 2. Символ на позиции $i$ цепочки должен совпадать с символом паттерна на позиции $i \bmod 3$ : позиция 0 — 'X', позиция 1 — 'Y', позиция 2 — 'Z', позиция 3 — снова 'X' и так далее.

Шаг 3. Программа:

pattern = "XYZ"
k = 3
with open('24.txt') as f:
 s = f.read()
count = 0
max_len = 0
j = 0
for ch in s:
 if ch == pattern[j]:
 count += 1
 j = (j + 1) % k
 else:
 if count > max_len:
 max_len = count
 if ch == pattern[0]:
 count = 1
 j = 1
 else:
 count = 0
 j = 0
if count > max_len:
 max_len = count
print(max_len)

Шаг 4. Ключевой момент: если очередной символ не совпал с ожидаемым по паттерну, нужно проверить — а вдруг он совпадает с началом нового паттерна (символ 'X')? Тогда новая цепочка стартует прямо с этого символа, а не с нуля. Это частая ловушка при решении подобных задач.

Шаг 5. После завершения цикла нужно ещё раз сравнить последнюю накопленную серию с максимумом — иначе можно потерять цепочку, которая заканчивается ровно в конце файла.

Ответ: 13.

Типичные ошибки и ловушки

Забыть сравнить последнюю серию с максимумом после выхода из цикла. Если самая длинная серия оказывается в самом конце файла, без этой проверки ответ будет занижен.
Неверная инициализация счётчика. В задачах на конкретный символ (метод 2) сброс счётчика должен быть в 0, а в задачах на чередование (метод 3) — часто в 1, поскольку текущий символ уже начинает новую потенциальную серию.
Игнорирование возможности начать новую цепочку сразу после обрыва паттерна. Как показано в примере 3, если очередной символ не подходит под продолжение цепочки, но подходит под её начало, серию нужно начинать заново с этого же символа, а не со следующего.
Медленное чтение файла посимвольно с накоплением строки через конкатенацию — при объёме до $10^6$ символов это может привести к превышению времени выполнения в некоторых языках программирования. Лучше читать файл целиком в память или использовать буферизированное построчное чтение.
Путаница между "строго чередующимися" и "просто разными" символами. В условии важно различать: нужно ли, чтобы каждый следующий символ отличался только от непосредственно предыдущего, или же вся цепочка должна состоять строго из трёх разных символов подряд без повторов на более длинном промежутке.
Неправильная обработка граничных случаев — файл может начинаться или заканчиваться прямо на границе искомой серии, а также быть полностью состоящим из одного повторяющегося символа.
Ошибки в индексации паттерна. При работе с повторяющимся паттерном важно аккуратно использовать операцию взятия остатка $i \bmod k$ , чтобы не выйти за границы длины паттерна.

Как готовиться

Изучи и запомни базовые шаблоны кода для подсчёта серий: одинаковых символов, чередующихся символов и повторяющихся паттернов. Эти три шаблона покрывают почти все вариации задания 24.
Потренируйся писать код без обращения к готовым решениям — сначала на маленьких строках, которые можно проверить вручную (5–10 символов), чтобы убедиться в правильности логики счётчиков.
Обязательно проверяй свою программу на крайних случаях: строка из одного повторяющегося символа, строка, которая идеально совпадает с паттерном от начала до конца, строка, где искомая серия находится в самом начале или в самом конце файла.
Прорешай побольше вариантов из открытого банка заданий и демонстрационных версий — большинство формулировок задания 24 сводятся к комбинации уже разобранных методов с небольшими изменениями условия.
Отработай навык быстрого чтения файла на выбранном языке программирования — знай заранее, как правильно открыть файл, прочитать его целиком и не потерять производительность на больших объёмах данных.
После написания программы всегда перечитывай условие ещё раз и сверяй логику алгоритма построчно — часто ошибка кроется не в синтаксисе, а в неверном понимании того, что именно считается "серией" в конкретной задаче.
Веди список типичных ловушек (как в разделе выше) и перед каждой тренировкой быстро пробегай его глазами — это помогает не наступать на одни и те же грабли.