Groups
Category
Level
The Sieve of Eratosthenes marks multiples of each prime to find all primes up to n in O(n log log n) time.
The greatest common divisor (gcd) of two integers is the largest integer that divides both without a remainder.
Matrix exponentiation turns repeated linear transitions into a single fast power of a matrix using exponentiation by squaring.
Small-to-large merging is a technique where you always merge the smaller container into the larger one to guarantee low total work.
Mo's algorithm answers many range queries offline by reordering them to minimize pointer movement along the array.
A line can be represented by two points, a point with a direction vector, or the general form ax + by + c = 0, and these forms are interconvertible.
The minimum rotation of a string is the lexicographically smallest string you can get by cutting it at some position and swapping the two parts.
The prefix function π of a string tells, for every position, the length of the longest proper prefix that is also a suffix of the prefix ending there.
The Z-function of a string S computes for each position i the length of the longest substring starting at i that matches the prefix of S.
The KMP algorithm finds all occurrences of a pattern in a text in O(n + m) time by never re-checking characters that are already known to match or mismatch.
Manacher's algorithm finds the length of the longest palindrome centered at every position in a string in linear time O(n).
Polynomial string hashing encodes a string as a base-p number modulo a large prime, letting us compare substrings in O(1) after O(n) preprocessing.