Задание EGEINF79DEC1: Обработка текстового файла

Решение.

Подходящий фрагмент обязан закончиться сразу после некоторого вхождения 2025. Переберём именно такие окончания. Для каждого из них нужны ровно 50 последних полных вхождений образца внутри фрагмента. У 2025 нет непустого собственного префикса, совпадающего с суффиксом, поэтому его вхождения не перекрываются.

Пусть текущее вхождение — пятидесятое или более позднее. Если перед последними 50 вхождениями есть ещё одно, его начало обозначим p. Самая ранняя разрешённая левая граница равна p + 1: так предыдущее вхождение уже не входит целиком, а все 50 следующих сохранены. Если предыдущего вхождения нет, начинаем с позиции 0. Нельзя отбрасывать весь предыдущий образец: его последние три символа разрешено оставить.

Этот самый длинный кандидат для выбранного окончания содержит не меньше букв Y, чем любой более короткий с тем же концом. Если в нём меньше 140 букв Y, сдвиг начала вправо не поможет. Если их не меньше 140, учитываем его длину. Такой выбор рассматривает оптимальный фрагмент для каждого возможного окончания.

Храним очередь из не более 51 пары: позиция начала очередного 2025 и число букв Y до этой позиции. При чтении строки обновляем общий счётчик Y. В самом образце буквы Y нет, поэтому к его концу счётчик остаётся тем же. Вычитание счётчика у исключённого предыдущего вхождения даёт число Y в выбранном фрагменте.

Проверка по исходному файлу: фрагмент на позициях 2936833–2937770 включительно, считая с 1, оканчивается на 2025. В нём 50 полных вхождений 2025 и 237 букв Y, то есть требуемые ограничения выполнены. Длина: 2937770 − 2936833 + 1 = 938.

Программа Python; переименуем извлечённый текстовый файл в data.txt либо укажем его исходное имя в open:

from collections import deque

with open("data.txt", encoding="utf-8-sig") as f:
    s = f.read().strip()
recent = deque(maxlen=51)
y_total = 0
best = 0
for i, ch in enumerate(s):
    if ch == "Y":
        y_total += 1
    if s.startswith("2025", i):
        recent.append((i, y_total))
        if len(recent) < 50:
            continue
        if len(recent) == 50:
            left = 0
            y_before = 0
        else:
            previous, y_before = recent[0]
            left = previous + 1
        if y_total - y_before >= 140:
            best = max(best, i + 4 - left)
print(best)

Программа проходит по строке за линейное время. Дополнительные счётчики и очередь ограниченной длины не растут с длиной файла. Независимый алгоритм по позициям символов и вхождений подтвердил максимум.

Ответ: 938.