Tries and String Algorithms

A trie is a prefix tree that stores strings by shared prefixes, giving O(length) lookup and natural prefix queries for autocomplete. The classic string-matching algorithms (KMP's failure function, Rabin-Karp's rolling hash) beat the naive O(nm) scan by never re-comparing characters they already know. Applied AI coding interviews probe these because they show up directly in tokenizer dictionaries, search indexes, and substring filters, and because candidates almost always reach for the brute-force scan first.