SPOJ PRHYME

SPOJ Problem Set (classical) 2737. Perfect Rhyme

A perfect rhyme is not a crime,
it is something that exceeds time,
a bit of science, a piece of art,
soft as a pillow, sharp as a dart.

I really love this little rhyme.

Basically the problem is, you are given a dictionary of words, and some query words. For each query word q, you have to find a dictionary word u such that, u != q and the common suffix of q and u are of maximum length possible. In case there is a tie, the problem requires the lexicographically smallest such word.

This problem can be solved using STL maps and storing the suffixes along with their sorted id, but there is a more elegant solution using Trie data structure, i.e. prefix tree. As we are interested in maximizing common suffix length, we can store the strings in the Trie in reversed form, so now the suffixes will become prefixes in this tree. For each dictionary word, we also need to store its index number, when sorted, as a termination marker for that word, so that, we can find the id of an word easily during the query. On each node, we also need to keep two additional information, the ids of lexicographically smallest and second smallest strings passing through that node, which we call min1 and min2. Initially both should contain an infinite value.

Now for each query word, we also search the word in reversed form. If it is not found in the tree, i.e. a path may exist, but the end marker is not present, then the task is simple, we just return the lexicographically smallest id, which is min1, from the current node, i.e. the node which we reached while trying to match the query string.

But extra cares should be taken when the query string is found on the tree, because, then we have to look for another candidate, for which, we have kept min2, i.e. second lexicographically smallest index. If we can deduce that, going to node x from current node cur, if it evidently means we will end up finding the exact same word, then we can't follow that path, instead, we decide which index to return from current node cur, if its min1 index refers to the word itself, then we return min2, otherwise we return min1. And if we have no other choice but end up at the exact matching point, then we are also sure that there is at least another string which follows the same path, but does not end at our current node, i.e. at least two different words. Then depending on our query word, we select min1 or min2 from our current node.

So, if you know how to code a Trie, it is not really a hard one, but indeed a tricky one.