3 ms·
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 fas
by ninepoints 3y ago
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...
- bonzini 3y agoI 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.
- deleted 3y ago[deleted]