Маршрутизатор сайта
Веб-сервер получает адрес страницы и должен решить, какой обработчик его покажет. Обработчики привязаны к маршрутам — началам адресов: маршрут /cs/basics отвечает за курс, а /cs/basics/strings — за одну его главу. Маршрут подходит к адресу, если совпадает с ним целиком или адрес продолжается после маршрута знаком /: части адреса между косыми чертами — сегменты — делить нельзя. Маршрут / подходит ко всем адресам. Из подходящих маршрутов выбирается самый длинный.
Второй и третий тесты — все 8966 адресов из карты этого сайта; маршруты — его разделы и страницы, адрес которых служит началом другого адреса внутри сегмента, как /cs/basics/strings и /cs/basics/strings-search. В третьем тесте маршрута / нет.
Вход
В первой строке m (1 ≤ m ≤ 10⁵) — число маршрутов. В следующих m строках — маршрут и имя обработчика. Дальше q (1 ≤ q ≤ 10⁵) и q строк с адресами. Маршруты и адреса начинаются с /, не кончаются на / (кроме самого /), не содержат пустых сегментов и пробелов; длина каждого — до 200 знаков. Маршруты разные. Имена обработчиков — из латинских букв, цифр, точек и дефисов.
Выход
Для каждого адреса — имя обработчика самого длинного подходящего маршрута или 404, если не подходит ни один.
Примеры
Пример 1
4 /blog blog /cs/basics/strings chapter-7 /cs cs /cs/basics course 6 /cs/basics/strings /cs/basics/strings-search /cs/algorithms /blog/notes /about /
chapter-7 course cs blog 404 404
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверять каждый маршрут для каждого адреса — до 10¹⁰ сравнений. Все маршруты, которые подходят к адресу, — его начала. Какая структура хранит много строк так, что все начала данной строки лежат на одном пути?
2Подсказка 2
Бор по буквам ищет начала, но маршрут /cs/basics/strings — начало адреса /cs/basics/strings-search по буквам, а подходить к нему не должен. Из каких «букв» должен состоять бор?
3Идея
Бор над сегментами: ребро подписано не буквой, а целым сегментом адреса. Маршрут — путь от корня по его сегментам, в конце пути — имя обработчика; маршрут / — сам корень. Адрес спускается по своим сегментам, пока есть куда, и запоминает последний встреченный узел с обработчиком: это и есть самый длинный подходящий маршрут.
4Разбор
Разбиваем строку по / и выбрасываем пустые куски — первый, перед ведущей косой чертой. В Python узел — словарь «сегмент → номер узла», в Go — map[string]int. Спуск обрывается на первом сегменте, которого нет в боре: дальше подходящих маршрутов не бывает, потому что каждый маршрут — путь от корня. Если ни одного узла с обработчиком на пути не было, ответ 404.
Маршрутизаторы веб-фреймворков тоже хранят маршруты в префиксных деревьях. Например, httprouter для Go держит их в сжатом дереве, где ребро подписано целой подстрокой, а параметры вида :id — отдельные узлы.
4+Решение
5Сложность
O(R + A) времени, где R и A — суммарные длины маршрутов и адресов (сегменты хешируются, поэтому шаг вниз — O(длины сегмента) в среднем). Память — O(R).
6Типичные ошибки
- Бор по буквам. Находит маршрут
/cs/basics/stringsдля адреса/cs/basics/strings-search— первый пример и второй тест. - Первый подходящий вместо самого длинного. Маршрут
/csподходит к любой главе курса, но нужен/cs/basicsили глава. - Корень. Маршрут
/подходит ко всему; если его нет (третий тест), ненайденные адреса —404. startswithпо всем маршрутам. Медленно на четвёртом и пятом тестах: десятки тысяч маршрутов на 50 000 адресов.