← All solutions

Solved by 54 teams.

First solved after 55 minutes.

Shortest team solution: 845 bytes.

Shortest judge solution: 1300 bytes.

There are at least two possible ways to solve this problem. The first, which was taken by most of the judges who solved the problem, is to sort the Royal Ladies. While a naïve sort could take O(n2 log n) time, one can use the same doubling approach normally used for building suffix arrays to perform the sort in O(n log n) time (or O(n log2 n) time if one uses a standard built-in sort instead of implementing counting sort). After this, binary search for each query in the sorted list; if the total length of the queries is L, then this part requires O( L log n) time.

In the other approach, we start by reversing all strings, so that each Lady’s name is formed by appending a letter to her mother’s name (rather than prepending), and the queries are for suffixes. The queries are all placed into a trie, with suffix links as in the Aho-Corasick algorithm. Now for each Lady in turn one can walk the trie to find the longest suffix that matches a node in the trie. There are a few more details to work out regarding query strings that are suffixes of other query strings, but overall the algorithm requires O(n) for a fixed-size alphabet.