KMP Algorithm
Learn KMP Algorithm (Strings, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Knuth-Morris-Pratt (KMP) Pattern Matching KMP finds all occurrences of a pattern in a text in O(n + m) time - guaranteed, no bad worst case like the naive O(n·m) approach. The key idea: precompute an LPS array (Longest Proper Prefix which is also a Suffix) for the pattern, so that on a mismatch, the algorithm knows exactly how far it can safely skip WITHOUT re-checking characters it already knows match.