String-searching algorithm

Summary

A string-searching algorithm, or string-matching algorithm, finds the places where a short string, the pattern, occurs inside a longer string, the text. The obvious method compares the pattern at every position and needs time $O(nm)$ for a text of length $n$ and a pattern of length $m$. Cleverer methods, such as the Knuth–Morris–Pratt algorithm, reach time $O(n + m)$ by reusing what earlier comparisons revealed. These algorithms underlie text editors, search tools and the analysis of DNA sequences.