For KMP pattern matching, O(n + m) means the work grows with the combined lengths of the text (n) and pattern (m). The text pointer never resets: after a mismatch, KMP uses the LPS array to reposition the pattern pointer and avoid repeating comparisons. The method is deterministic and does not need hash functions. section 5.1.1
Finding a pattern
For text “abcxabc dabxabcdabcdabcy” and pattern “abcdabcy,” KMP uses LPS-based shifts after mismatches and finds the pattern starting at index 15. section 5.1.1
