I've recently been working on directed acyclic word graphs. They are a small modification to tries and can be built with (I think) the same time complexity. For

I've recently been working on directed acyclic word graphs. They are a small modification to tries and can be built with (I think) the same time complexity. For each node, count the distance from EOW when building, maintain a list of nodes with the same EOW distance and merge the ones that are equal strings. They use much less space by sharing suffixes as well as prefixes. http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://en.wikipedia.org/wiki/Directed_acyclic_word_graph