dsa2 min read
KMP Algorithm — O(n+m) Pattern Matching with Failure Function
Implement KMP string search: build the failure function (LPS array) in O(m) then search in O(n). Never re-examines matched characters unlike naive search.
Read →
All Posts
1276 articles
dsa2 min read
Z-Algorithm — Linear Prefix Matching for All Positions
The Z-algorithm computes Z[i] = length of the longest substring starting at i that matches a prefix of the string. O(n) time, elegant and powerful for pattern search.
Read →
dsa2 min read
Rabin-Karp — Rolling Hash for Pattern Matching and Substring Search
Rabin-Karp uses a rolling polynomial hash to match patterns in O(n+m) expected time. The key is updating the hash in O(1) as the window slides.
Read →
dsa2 min read
Manacher's Algorithm — Longest Palindromic Substring in O(n)
Find the longest palindromic substring in O(n) using Manacher's algorithm. Expands palindromes using a mirror trick to avoid redundant work.
Read →
dsa2 min read
String Hashing — Polynomial Hash for O(1) Substring Comparison
Precompute polynomial prefix hashes to compare any two substrings in O(1). Enables O(n log n) LCP computation and O(n) duplicate detection.
Read →
Page 231 of 256