The Knuth–Morris–Pratt Algorithm

The string matching problem is a fundamental challenge in computer science with extensive applications ranging from text retrieval systems to computational biology. Given a large text string T of length n and a shorter pattern string P of length m, the primary objective is to identify all valid shifts or indices where P occurs within T.

While the naive approach evaluates character alignments sequentially—resulting in a worst-case time complexity of O(n × m)—more sophisticated linear-time algorithms have been engineered. Developed by Donald Knuth, Vaughan Pratt, and James H. Morris in 1977, the Knuth-Morris-Pratt (KMP) algorithm optimizes pattern searching by entirely eliminating redundant character comparisons. By leveraging structural features extracted from the pattern itself during a preprocessing phase, KMP ensures that the text pointer never backtracks, achieving a deterministic linear runtime of O(n + m).