Задание 24 ЕГЭ по информатике · 4D2418
Подстрока и буквы: мин./макс. длинаПовышеннаяКЭС 2.13КЭС 2.14
Задание выполняется с использованием прилагаемых к заданию файлов.
Текстовый файл состоит не более чем из 1 200 000 символов X, Y, и Z.
Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY.
Для выполнения этого задания следует написать программу.
613_24_4D2418.txtТекстовый файл состоит не более чем из 1 200 000 символов X, Y, и Z.
Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY.
Для выполнения этого задания следует написать программу.
Показать ответ
1713
Подсказки (3)
- Как изменяется допустимый фрагмент после обнаружения очередного вхождения подстроки XZZY?
- Просматривайте строку слева направо и храните позицию последнего обнаруженного вхождения XZZY.
- Для каждого символа вычисляйте длину фрагмента от позиции после последнего запрещённого вхождения до текущей позиции и запоминайте максимум.
Решение
1. Нужно найти самый длинный фрагмент строки, в котором не встречается XZZY. При последовательном просмотре достаточно отслеживать последнее положение окончания найденной подстроки XZZY. 2. Если подстрока XZZY заканчивается в позиции i, то новый допустимый фрагмент может начинаться только после предыдущего вхождения. Для поиска вхождений удобно проверять последние четыре символа строки. 3. После каждого символа вычисляем текущую длину допустимого фрагмента и обновляем максимум. Алгоритм работает за O(n) по времени и использует O(1) дополнительной памяти.
Частые ошибки
- Поиск только первого вхождения XZZY вместо всех вхождений.
- Неверное обновление левой границы после обнаружения запрещённой подстроки.
- Использование алгоритма с многократным перебором всей строки, что может привести к превышению времени работы.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
24Текстовый файл состоит не более чем из 1200000 символов, которые являются прописными буквами латинского…Подстрока и буквы: мин./макс. длина24Текстовый файл состоит не более чем из 1200000 символов, которые являются прописными буквами латинского…Подстрока и буквы: мин./макс. длина24Текстовый файл состоит не более чем из 10^(6) символов X, Y и Z. Определите максимальное количество идущих…Подстрока и буквы: мин./макс. длина24Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1…Подстрока и буквы: мин./макс. длина · 347F2224Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом…Подстрока и буквы: мин./макс. длина · 5605A024Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом…Подстрока и буквы: мин./макс. длина · 79DEC124Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1…Подстрока и буквы: мин./макс. длина · 98C51824Задание выполняется с использованием прилагаемых к заданию файлов. Текстовый файл состоит не более чем из 1…Подстрока и буквы: мин./макс. длина · A520F8
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.