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 →
Pattern-matching
2 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 →