Trie
A prefix tree that shares paths between strings
Characters live on a path
Each trie edge represents one character. Following a word from the root reaches its prefix node, while a terminal marker distinguishes a complete stored word from a prefix that only leads to longer words. Common prefixes share the same nodes.
Try it
Enter a word for exact search, or a prefix to list its completions.
Insertion and exact lookup take O(L) time for a string of length L, independent of the number of stored words. Enumerating completions additionally costs the size of the returned prefix subtree.
Use a trie for: autocomplete, dictionary lookup, prefix routing, and multi-pattern preprocessing. Its speed trades against the memory required by child references.
Aho-Corasick augments a trie with failure links to search many patterns through one text in a single pass.