Concepts158
Mo's Algorithm
Mo's algorithm answers many range queries offline by reordering them to minimize pointer movement along the array.
Rectangle Union Area
The union area of many axis-aligned rectangles can be computed efficiently using a sweep line over x and a segment tree tracking covered y-length.
Basic Geometry - Lines and Segments
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.
Suffix Array Construction
A suffix array stores the starting indices of all suffixes of a string in lexicographic order, enabling fast substring queries and many string operations.
Minimum Rotation
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.
KMP - Prefix Function Applications
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.
Z-Function
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.
KMP Algorithm
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
Manacher's algorithm finds the length of the longest palindrome centered at every position in a string in linear time O(n).
Slope Trick
Slope Trick is a technique to maintain a convex piecewise-linear function implicitly using two heaps and a running constant.
String Hashing (Polynomial Hash)
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.
Subset Sum Convolution
Subset Sum Convolution (often called Subset Convolution) computes C[S] by summing A[T]×B[U] over all disjoint pairs T and U whose union is S.