= String-searching algorithm
A <string-searching algorithm> locates occurrences of a pattern in a text, typically requiring a contiguous substring match. For text `ababa` and pattern `aba`, zero-based matches start at zero and two; overlaps count unless excluded by the specification. The direct <algorithm> compares the pattern at each start and can require $O(nm)$ character comparisons. The <Knuth-Morris-Pratt algorithm> reuses prefix information for linear total scanning work. State the alphabet, case handling and empty-pattern convention: matching bytes, <Unicode> code points and user-perceived characters can describe different tasks.
Back to article page
