Задание 24 ЕГЭ: минимальный фрагмент строки

Минимальный фрагмент с заданным числом сочетаний. Тема номера — обработка символьных строк. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Текстовый файл 24.txt содержит строку из заглавных латинских букв A, B, C, D, E, всего не более 20 000 символов.

Определите минимальное количество идущих подряд символов, среди которых сочетание символов CD встречается не менее 16 раз.

Для выполнения этого задания следует написать программу.

Скачать файл к примеру

Решение

Запоминаем позиции всех вхождений «CD». Самый короткий фрагмент с k вхождениями начинается в начале одного вхождения и заканчивается в конце k-го по счёту, поэтому достаточно перебрать k подряд идущих вхождений.

Ответ: 187.

s = open('24.txt').read().strip()
pat, k = 'CD', 16
pos = [i for i in range(len(s)) if s.startswith(pat, i)]
print(min(pos[i + k - 1] + len(pat) - pos[i] for i in range(len(pos) - k + 1)))

Решить такую задачу — новый вариант с проверкой