Strings
Pattern matching & palindromes
KMP
Knuth-Morris-Pratt: precomputes a longest-prefix-suffix table so a mismatch never rescans the text — linear-time pattern matching.
Time O(n + m) · Space O(m)
Rabin-Karp
Hashes the pattern and each text window with a rolling hash, verifying character-by-character only when hashes collide.
Time O(n + m) avg · Space O(1)
Z-Algorithm
Computes, for every position, the length of the longest substring starting there that matches a prefix of the string — reusing a [l, r) window.
Time O(n) · Space O(n)
Boyer-Moore
Compares the pattern right to left and uses the bad-character table to leap past hopeless alignments — often sublinear in practice.
Time O(n/m) best · Space O(σ)
Manacher's Algorithm
Finds the longest palindromic substring in linear time by expanding around centers and mirroring radii across the current palindrome.
Time O(n) · Space O(n)