The hash table solution permits an O(n) average solution if you change the hash function to be one that is incrementally computable (most are). Probably way faster than a trie of your entire corpus also...
I think the lookup would involve a string comparison if the hash matches, and that is also O(n). You should be able to construct a pathological example that ends up quadratic.
