First of all, a brute force solution that answers a query by traversing the entire wordlist should work fine if the number of queries is small. This was enough to solve the easy input.
For the hard input, such a program probably would not finish in time until the end of the contest, thus we need to find a solution that’s much faster.
We will first explain a solution that is fast enough and easy to implement.
We will start by reversing all words in our wordlist and sorting it. Now, words that rhyme are close in the sorted order, and the more they rhyme, the closer they are. More precisely, words with the same first K characters (which were originally the last K characters) always form a contiguous subsequence.
Now whenever processing a new query, we can easily find its place in the wordlist using binary search. Now, we can take a look on the words just before and after our position. No other word can have a longer common prefix with our word. Take the longer of these two prefixes. Now we can simply traverse the range of words that share it, and pick the first one lexicographically. (Note that in this step we compare the originals, not the reversed words.) As the wordlist contains English words, this range is never too long.
One solution with a better worst case time complexity is to insert the reversed words from the wordlist into a trie, process the trie bottom up so that in each vertex we know the lexicographically smallest of the words that end in its subtree, and then to look for the reverse of a query word in that trie.