Журнал нажатий
Текстовый редактор на всякий случай записывает каждое нажатие клавиши в журнал: если программа упадёт, документ можно будет восстановить, проиграв журнал с начала. Сегодня программа упала. Восстановите документ.
Документ сначала пуст, курсор стоит в его начале. Каждый символ журнала — одно нажатие:
<— курсор на один символ влево,>— на один вправо;[— курсор в начало документа,]— в конец;#— стереть символ слева от курсора;- любой другой символ, включая пробел, печатается там, где стоит курсор, и курсор оказывается сразу после него.
Нажатие, которое нечего делать (влево в самом начале, стереть в самом начале, вправо в самом конце), не меняет ничего. Третий и четвёртый тесты — журнал машинистки, которая набирала первые главы «Войны и мира»: опечатки она исправляет то сразу, то через несколько букв, а заголовок допечатывает в самом конце работы.
Вход
Одна строка — журнал длиной от 1 до 10⁶ символов в UTF-8. Символов <, >, [, ], # в тексте документа не бывает: в журнале они всегда означают клавиши.
Выход
Документ после всех нажатий одной строкой (пустой, если в документе ничего не осталось).
Примеры
Пример 1
и мр<и>[война ]!!#
война и мир!
Пример 2
#<[кот]>>#<<<
ко
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Вставлять в середину списка Python или строки — значит сдвигать весь хвост. Сколько это будет стоить, если половину текста напечатать в его начало?
2Подсказка 2
Известная хитрость для редактора — два стека: всё, что левее курсора, и всё, что правее. Буква, стирание, шаг влево и вправо стоят O(1). А сколько стоят [ и ]?
3Идея
Нужна структура, в которой и вставка у курсора, и прыжок в начало или в конец стоят O(1). Это двусвязный список со стражем: страж замыкает список в кольцо, его сосед справа — первая буква, сосед слева — последняя. Курсор — ссылка на узел, перед которым он стоит; курсор перед стражем — это конец документа.
4Разбор
Узлы удобно держать не объектами, а номерами в трёх массивах: ch, prev, next; узел 0 — страж. Новая буква получает следующий свободный номер, и вставка перед узлом at переписывает четыре ссылки: две у нового узла, next у его левого соседа и prev у at. Стирание выкидывает узел prev[at], связав его соседей, — две ссылки. Влево — at = prev[at], если слева не страж; вправо — at = next[at], если at не страж. В начало — at = next[0], в конец — at = 0. В конце проходим от стража по next и печатаем.
Стёртые узлы так и остаются в массивах, просто на них больше никто не ссылается; всего узлов не больше длины журнала, так что память — O(n). Массивы номеров вместо объектов в Python ещё и быстрее: создать объект узла дороже, чем записать число в готовую ячейку, и на шестом тесте версия с объектами вдвое медленнее.
4+Решение
5Сложность
O(n) на весь журнал: каждое нажатие — O(1), итоговый текст печатается одним проходом. Память O(n).
6Типичные ошибки
- Список Python и индекс курсора.
insertиdelв середине сдвигают хвост. Шестой тест печатает полмиллиона букв в начало длинного текста: каждая сдвигает по полмиллиона ячеек. Сдвиг — быстрая копия памяти, и на коротких журналах это незаметно, но здесь выходит четверть триллиона перемещённых ячеек. - Два стека. Классическое решение для редактора без клавиш «в начало» и «в конец». Здесь каждое
[перекладывает весь левый стек в правый, а седьмой тест прыгает между концами сто тысяч раз. Это тот же буфер с разрывом, что в Emacs: он хорош, пока правки рядом друг с другом. - Пробел в журнале. Пробел — тоже буква: не разбивайте строку по пробелам и не обрезайте её, кроме перевода строки в конце.
- Пустой документ. Девятый тест стирает и двигает курсор в пустом документе — ни одна из этих клавиш не должна падать.