Решение: Максимальная подстрока без шаблона
Задание выполняется с использованием прилагаемых к заданию файлов.
Текстовый файл состоит не более чем из 1 200 000 символов X, Y и Z.
Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY.
Для выполнения этого задания следует написать программу.
Решение по шагам
4 шагаНужно найти самый длинный фрагмент строки, в котором не встречается XZZY. При последовательном просмотре достаточно отслеживать последнее положение окончания найденной подстроки XZZY.
Если подстрока XZZY заканчивается в позиции i, то новый допустимый фрагмент может начинаться только после предыдущего вхождения. Для поиска вхождений удобно проверять последние четыре символа строки.
После каждого символа вычисляем текущую длину допустимого фрагмента и обновляем максимум. Алгоритм работает за O(n) по времени и использует O(1) дополнительной памяти.
Числовой ответ определяется содержимым прилагаемого текстового файла; его содержимое в исходных материалах не предоставлено.
Определяется по содержимому прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Поиск только первого вхождения XZZY вместо всех вхождений.
Неверное обновление левой границы после обнаружения запрещённой подстроки.
Использование алгоритма с многократным перебором всей строки, что может привести к превышению времени работы.