Текстовый файл состоит не более чем из 1200000 символов X, Y, и Z. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY. Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.
Решение:
Идея решения будет состоять в следующем. Мы будем проходить по файлу, пока не дойдем до конца. Каждый раз мы будем набирать по символу временную буферную строку с помощью конкатенации старого варианта этой строки с новым символом, с учетом того, что в текущую строчку не должна входить подстрока «XZZY». По ходу дела будем считать количество символов в текущей строке.
Если же мы найдем эту подстроку, то мы должны уменьшить счетчик на 1, т.к. если строка XZXXXXZXYZYXYZXZXXZZY уже НЕ подходит, то предыдущая строка XZXXXXZXYZYXYZXZXXZZ (без Y) уже подходит нам.
Далее мы сравниваем длину текущей строки с максимальной, и если она превышает текущий максимум, то обновляем его.
Далее заключается небольшой подвох, на котором можно попасться и допустить ошибку. Обнуляю буферную строку, НЕ нужно обнулять счетчик. Потому что к новой строке мы можем добавить 3 последних символа из предыдущего вхождения «XZZY», то есть учесть ZZY. А именно учесть их в размер следующей строки.
Для определения наличия одной подстроки s в какой-либо строке-источнике source, напишем следующую функцию:
Тогда всё решение можно реализовать в виде следующей программы:
Использование функции и набор/обновление буферной строки увеличивает память и время, которые используются программой. Поэтому в качестве альтернативного решения, можно пройтись по всему файлу, сдвигая группу из 4-х символов, как будто считывающую каретку магнитофона. Тогда нам не понадобится накапливать строку, которая (в теории) может состоять почти из всех символов файлов, что, возможно, повлечет за собой переполнение или потерю данных, если в ЯП будут предусмотрены средства ограничения максимального числа символов для одной строковой переменной.
Даже если не происходит переполнения и всё хорошо, группа из четырех символов использует гораздо меньше памяти в текущий момент времени. Попытаюсь сделать рисунок данной идеи:
Полная реализация кода будет следующей:
Запуск такой программы дает такой же результат.
Понравился разбор задач? Проявите активность: лайк, репост, комментарий.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram