The site's router
A web server receives a page address and must decide which handler will show it. Handlers are bound to routes, beginnings of addresses: the route /cs/basics is responsible for the course, and /cs/basics/strings for one of its chapters. A route matches an address if it coincides with it entirely or the address continues after the route with a /: the parts of an address between slashes, segments, cannot be split. The route / matches all addresses. Of the matching routes, the longest is chosen.
The second and third tests are all 8966 addresses from this site’s sitemap; the routes are its sections and the pages whose address is the beginning of another address within a segment, like /cs/basics/strings and /cs/basics/strings-search. The third test has no route /.
Input
The first line holds m (1 ≤ m ≤ 10⁵), the number of routes. The next m lines hold a route and a handler name. Then q (1 ≤ q ≤ 10⁵) and q lines with addresses. Routes and addresses begin with /, do not end with / (except / itself), and contain no empty segments or spaces; each is up to 200 characters long. Routes are distinct. Handler names consist of Latin letters, digits, dots and hyphens.
Output
For each address, the name of the handler of the longest matching route, or 404 if none matches.
Examples
Example 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
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Checking every route against every address is up to 10¹⁰ comparisons. All the routes that match an address are its beginnings. What structure stores many strings so that all the beginnings of a given string lie on one path?
2Hint 2
A trie finds beginnings letter by letter, but the route /cs/basics/strings is a beginning of the address /cs/basics/strings-search letter by letter and must not match it. What “letters” should the trie be made of?
3The idea
A trie over segments: an edge is labelled not with a letter but with a whole segment of the address. A route is a path from the root along its segments, with the handler name at the end of the path; the route / is the root itself. An address descends by its segments as far as it can and remembers the last node with a handler it met: that is the longest matching route.
4Walkthrough
Split the string by / and throw away the empty pieces, the first one before the leading slash. In Python a node is a “segment → node number” dictionary, in Go a map[string]int. The descent stops at the first segment not in the trie: no further routes can match, because every route is a path from the root. If there was no node with a handler on the path, the answer is 404.
Web framework routers also store routes in prefix trees. For example, httprouter for Go keeps them in a compressed tree where an edge is labelled with a whole substring, and parameters like :id are separate nodes.
4+Solution
5Complexity
O(R + A) time, where R and A are the total lengths of the routes and the addresses (segments are hashed, so a step down is O(length of the segment) on average). Memory is O(R).
6Common mistakes
- A letter-by-letter trie. It finds the route
/cs/basics/stringsfor the address/cs/basics/strings-search: the first example and the second test. - The first match instead of the longest. The route
/csmatches any chapter of the course, but/cs/basicsor the chapter is needed. - The root. The route
/matches everything; if it is absent (the third test), addresses not found get404. startswithover all routes. Slow on the fourth and fifth tests: tens of thousands of routes for 50,000 addresses.