Advanced · Module 19
Tries and string algorithms
Prefix trees, rolling hashes and linear-time pattern matching.
Strings have structure that general-purpose tools ignore: shared prefixes, repeated blocks, and suffixes that overlap. This module uses it. Tries share prefixes between words and drive searches over whole dictionaries; rolling hashes turn windows of text into numbers; the prefix function lets KMP search without ever moving backward; and suffix arrays index every substring of a text for repeated queries. Each comes with its costs and the cases where something simpler is enough.
- 1TriesPro — members onlyA trie stores strings as paths from a root, one character per edge, so words with a common prefix share nodes. Lookups and prefix queries cost time proportional to the query's length, however many words are stored.14 min
- 2Rolling hash and Rabin-KarpPro — members onlyA rolling hash updates the hash of a sliding window in constant time as one character leaves and another enters. Rabin-Karp uses it to compare a pattern against every window of a text, checking characters only when the hashes match.14 min
- 3KMP and prefix functionsPro — members onlyThe prefix function records, for every position of a pattern, the longest proper prefix that is also a suffix there. Knuth-Morris-Pratt uses it to search a text without ever moving backward, in O(n + m) time in the worst case.15 min
- 4Suffix arrays in practicePro — members onlyA suffix array lists the starting positions of a text's suffixes in sorted order. With the LCP array beside it, it answers substring search, repeated substrings and distinct-substring counts, and it underlies genome search tools.15 min