The reverse trie — i.e., suffix tree (and related suffix array) — is genius. But a good hash table is almost certainly the way to go. Maybe a wicked good engineer can write this algorithm using a suffix array that actually performs faster than a good hash table with a string compare... but most will miss cache and branch mispredict all over the place.
Also can we discuss why we would want someone to write a trie or any of these solutions rather than using something like a dict? If I saw some convoluted solution like this in a PR there better be a really good reason for it.
