Concepts7
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).
Tree DP - Matching and Covering
Tree DP solves matching, vertex cover, and independent set on trees in linear time using small state transitions per node.
2-SAT
2-SAT solves Boolean formulas where every clause has exactly two literals, and it is solvable in linear time relative to the size of the implication graph.
Two Pointers
Two pointers is a pattern where two indices move through a sequence in a coordinated, usually monotonic way to avoid unnecessary work.
Monotonic Deque
A monotonic deque is a double-ended queue that keeps elements in increasing or decreasing order so that the front always holds the current optimum (min or max).