liveBook · Manning

O(n + m)

As explained in Algorithms Every Programmer Should Know

A time bound proportional to the combined lengths n and m of two inputs.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains the linear bound through pointer movement and LPS-based mismatch handling, without deriving a formal proof.
Examples
Trace KMP searching for “abcdabcy” and locating its match at index 15.
What you can do after
Apply KMP to search for a pattern with work proportional to the text and pattern lengths.
How it connects
Connects KMP pattern matching with the LPS array and contrasts it with Rabin–Karp.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.