String-searching algorithm

Definition

Let $\Sigma$ be a finite alphabet. Let $P = p_1 \cdots p_m$ and $T = t_1 \cdots t_n$ be strings over $\Sigma$ with $1 \le m \le n$ ; $P$ is the pattern and $T$ is the text. The pattern occurs at position $i$ of $T$ , where $1 \le i \le n - m + 1$ , if $t_{i + j - 1} = p_j$ for all $j = 1, \dots, m$ . A string-searching algorithm is an algorithm that, given $P$ and $T$ , outputs the set of all positions at which $P$ occurs in $T$ .

Remarks

Example: the naive algorithm checks, for each $i = 1, \dots, n - m + 1$ , the $m$ equalities $t_{i + j - 1} = p_j$ in turn. It outputs exactly the positions of occurrence, so it is a string-searching algorithm, and it uses $O(nm)$ comparisons. For $T = abracadabra$ and $P = abra$ it outputs $\set{1, 8}$ .

Non-example: a procedure that stops and outputs the first position of an occurrence solves only the weaker problem of finding one occurrence, not all of them.

Many variants exist: searching for several patterns at once, as in the Aho–Corasick algorithm, or allowing a bounded number of mismatches.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Algorithm concept
Alphabet concept
String concept
String-searching algorithm definition

Tag	`R75EQC05SX`
URI	`m2://R75EQC05SX`
Kind	definition
Writing	W0 stub
MSC	68W32, 68R15, 68W40
Defines	String-searching algorithm
Uses	Alphabet, String, Algorithm
Changed	3 November 2026

String-searching algorithm

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here