String and Math Algorithms
Pattern matching, hashing, number theory, combinatorics and computational geometry.
This is an overview — pick a sub-topic below.
Sub-topics (18)
KMP Algorithm
Knuth-Morris-Pratt pattern search in $O(n + m)$ using a prefix (failure) function.
Rabin-Karp Algorithm
Pattern search using rolling hashes; compare strings only when hashes match.
Z Algorithm
Computes for each position the length of the longest substring matching a prefix, in $O(n)$.
Boyer-Moore Algorithm
Pattern search scanning from the pattern's end and skipping ahead using bad-character and good-suffix rules.
Manacher's Algorithm
Finds the longest palindromic substring in $O(n)$.
Rolling Hash
Update a substring's hash in $O(1)$ when the window slides.
Suffix Automaton
The smallest automaton accepting all substrings of a string, built in $O(n)$.
GCD and LCM
Greatest common divisor via Euclid's algorithm; $\text{lcm}(a,b) = a/\gcd(a,b)\cdot b$.
Sieve of Eratosthenes
Find all primes up to $n$ by crossing out multiples — $O(n\log\log n)$.
Prime Factorization
Break a number into prime factors by trial division up to $\sqrt n$, or using a smallest-prime-factor sieve.
Modular Arithmetic
Arithmetic with remainders: $(a+b)\bmod m$, $(a\cdot b)\bmod m$, and modular inverses.
Fast Exponentiation
Compute $a^b$ in $O(\log b)$ by squaring.
Combinatorics
Counting arrangements and selections.
Permutations and Combinations
Order matters (permutations, $n!/(n-k)!$) vs doesn't (combinations, $\binom nk$).
Matrix Exponentiation
Raise a matrix to a power in $O(k^3\log n)$ to solve linear recurrences fast.
Geometry Algorithms
Points, vectors, lines and polygons computed with cross products.
Convex Hull
The smallest convex polygon containing all points.
Line Sweep
Process geometric events sorted along one axis while maintaining an active set.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.