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

Решение.
В приложенном файле 1100000 символов данных. Рассматриваем непрерывные фрагменты строки; символы нельзя переставлять или пропускать. Сохраним приложенный текстовый файл под именем data.txt. Конечный перевод строки удаляем, остальные символы сохраняем.
Недопустимое сочетание описывается шаблоном KM|MK; его длина равна 2. Будем хранить left — наименьший допустимый индекс начала фрагмента при фиксированном правом конце.
Если запрещённое сочетание начинается в позиции i, то фрагмент, заканчивающийся в позиции i + 1, обязан начинаться правее i. Присваиваем left = i + 1. До конца этого сочетания максимальный допустимый фрагмент заканчивается в позиции i + 0. Его длина равна i + 1 − left, где left ещё имеет прежнее значение.
Используем поиск с просмотром вперёд: он находит также перекрывающиеся вхождения. Например, в трёх одинаковых буквах есть две соседние пары одинаковых букв, а не одна. После последнего запрещённого сочетания отдельно проверяем хвост до конца файла. Таким образом, учтены обе границы файла и все промежутки.
Программа:

import re

with open("data.txt", encoding="utf-8-sig") as f:
    s = f.read().rstrip("\r\n")
left = 0
answer = 0
for match in re.finditer('(?=(KM|MK))', s):
    i = match.start()
    answer = max(answer, i + 1 - left)
    left = i + 1
answer = max(answer, len(s) - left)
print(answer)

Проверка результата. Нумеруем символы исходной строки с единицы. Один из оптимальных фрагментов имеет следующие границы:

Разность границ с учётом обоих концов: 913247 − 913136 + 1 = 112.
В найденном фрагменте нет ни одного запрещённого сочетания. Во всём файле найдено 138160 запрещённых вхождений; проверены промежутки между ними, начало и конец файла.
Полный проход по приложенному файлу даёт итоговый ответ. Проверка коротких строк полным перебором всех подстрок подтверждает обработку крайних случаев.
Ответ: 112.