Built on
trie
Articles
SRT
Algorithm
Counting sort and radix sort
Without comparisons: count the keys or split them into digits, O(n + k) and O(d·n) instead of n log n.
O(n + k) and O(d·(n + b))
2 problems
STR
Algorithm
The Aho–Corasick algorithm
Every occurrence of thousands of words in one pass: a trie of the words plus failure links, as in the prefix function.
O(n + Σ|wᵢ| + z)
1 problem
Problems
Often together
classic 2 in production 2 sorting 1 array 1 stable 1 prefix sums 1 bit tricks 1 version control 1 interviews 1 string matching 1 automaton 1 streaming 1