Concepts80
Category
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.
Point in Polygon
Point-in-polygon decides whether a point lies outside, inside, or on the boundary of a polygon.
Orientation and CCW
Orientation (CCW test) tells whether three points make a left turn, right turn, or are collinear by using the sign of a 2D cross product.
Basic Geometry - Points and Vectors
A 2D point can be treated as a vector from the origin, so vector math (addition, scaling, dot, cross) applies directly to points.
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).
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.
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.
Interval DP
Interval DP solves problems where the optimal answer for a segment [i, j] depends on answers of its subsegments.
Tree DP - Rerooting Technique
Rerooting (a.k.a. 换根 DP) computes a per-node answer as if each node were the root, in total O(n) time on trees.