the exact string-matching problem

You have a long page of text and you want to find every place a particular word appears in it. That is the everyday face of exact string matching: given a big string (call it the text) and a short string (call it the pattern), report every position in the text where the pattern occurs as a contiguous block of characters. Your text editor's Find command, a search inside a log file, and DNA database lookups are all asking this same question.

Stated precisely: we are given a text T of length n and a pattern P of length m, both over some alphabet (the set of allowed characters, like the 26 letters or the four DNA bases A, C, G, T). We must output every shift s (a starting index) such that the m characters T[s], T[s+1], ..., T[s+m-1] are exactly P[0], P[1], ..., P[m-1] in order. 'Exact' means character-for-character identical — no typos, no wildcards, no gaps. A position is called an occurrence or a match. There can be zero matches, one, or many, and matches may even overlap (the pattern 'aa' occurs at positions 0 and 1 in 'aaa').

This is one of the most-run computations on Earth, so the difference between a slow and a fast method matters enormously. The simplest approach checks every starting position and can cost about O(n*m) in the worst case; the clever algorithms in this field (Knuth-Morris-Pratt, the Z-algorithm, Rabin-Karp, Boyer-Moore, Aho-Corasick) push this down to O(n+m) or even sublinear on typical inputs, by never re-examining characters they have already learned about. Keep the problem statement separate from any one algorithm: the problem is the question, and there are many algorithms that answer it with different trade-offs.