Concepts318
Category
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.
Aliens Trick (WQS Binary Search)
Aliens Trick (WQS Binary Search) converts a hard βexactly k itemsβ optimization into an unconstrained problem by adding a penalty Ξ» per chosen item.
Exchange Arguments in DP
An exchange argument proves that any optimal solution can be reordered to satisfy a simple sorting rule by showing that swapping adjacent out-of-order elements never helps.
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.
Divide and Conquer DP Optimization
Divide and Conquer DP optimization speeds up DP transitions of the form dp[i][j] = min over k of dp[i-1][k] + C(k, j) when the optimal k is monotone in j.
Convex Hull Trick - Dynamic (LineContainer)
Dynamic Convex Hull Trick (LineContainer) maintains the lower or upper envelope of lines y = m x + b with O(log n) insertion and O(log n) query for arbitrary insertion order.
Convex Hull Trick (CHT)
The Convex Hull Trick (CHT) speeds up dynamic programs where each state is a minimum over linear functions, such as dp[i] = min_j (dp[j] + b[j] Γ a[i]).