Failure-function

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.