The correct answer in that case is "aa".

I haven't thought of a good solution yet. Apparently there can be up to 5 million letters in the whole input, so traversing the whole tree for every word will be too slow. I designed an algorithm like that and tried it out to check the speed, but stupid SPOJ is giving me wrong answer, as usual, probably because there's an extra newline, a missing new line or a mosquito flew by.

I tried every possible input I found on the Internet and my program always gives the right answer, but yet the crystal delicate SPOJ checker is giving me WA.

Then there's the easier solution of mapping every suffix to the shortest word that matches using map...

But it can be solved using trie too, reversing all words and storing at every node of the trie the two minimal words that are contained in that subtree (two are required in case one of them is the prefix we are looking itself).