prefixmatching

Prefix matching is the problem of determining whether a given string starts with a specified prefix, and of retrieving all strings in a collection that share that prefix. It is used in text search, autocomplete, spell checking, command-line interfaces, and data routing, among other areas. A prefix match can be performed by straightforward character-by-character comparison, but practical systems use data structures that support many queries efficiently.

The most common structure for prefix matching is the prefix tree, or trie. In a trie, each node represents a character and a path from the root to a node spells a prefix. To test a prefix of length k, one follows k edges, yielding O(k) time. To enumerate all strings with that prefix, one traverses the subtree under the corresponding node. Alternative approaches include storing sorted strings and using binary search to locate the range of strings starting with the prefix, or using radix or Patricia tries for more compact representations.

Variants include exact prefix existence, retrieval of all matches, and longest-prefix matching, notably in IP routing, where the goal is to find the longest stored prefix that matches a query string.

Performance considerations depend on data size and usage patterns. Tries provide fast prefix lookup with predictable time but higher memory usage. Sorting and binary search reduce memory needs but incur O(log n) search time plus O(m) per string comparison, where m is the prefix length.

Applications span autocomplete systems, dictionaries, spell-checkers, code editors, and networking routing protocols that rely on prefix matching for routing decisions.