Поиск минимального фрагмента
Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$.
Определите минимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов $AB$ (в указанном порядке) встречается ровно 220 раз.
Для выполнения этого задания следует написать программу.
Условие как в банке ФИПИ — открыть и сверить
| |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Как можно быстро посчитать количество вхождений пары $AB$ в каждом рассматриваемом фрагменте?
2Наводящая — какие числа считатьуровень 2 из 3
Рассматривайте файл как строку и используйте префиксные суммы: для каждой позиции подсчитайте, начинается ли там пара $AB$.
3Прямая — фактически решениеуровень 3 из 3
Для каждой левой границы найдите минимальную правую границу, на которой число пар $AB$ становится равным 220. Выберите наименьшую длину полученного фрагмента.