For the trie, things would be a lot better if the words got longer. All the 'inefficiencies' of a trie lie in the pointer chasing. The great thing is that you c

For the trie, things would be a lot better if the words got longer. All the 'inefficiencies' of a trie lie in the pointer chasing. The great thing is that you can process a string 'on-line'. If things start getting really big, there are some tricks with LCP-arrays and constant time RMQ (range minimal query) that have great theoretical performance. I haven't seen that stuff in practice though.