String Matching Problem

Definition

String Matching Problem

Given a text string $T=t_1{t}_2\dots t_n$ and a pattern string $P=p_1{p}_2\dots p_m$ over an alphabet $\Sigma$. The string matching problem asks for all indices $i$ such that $P$ occurs in $T$ starting at position $i$, i.e. $T[i..i+m-1]=P$.

Input: $(T,P)\in {\Sigma }^{\ast }\times {\Sigma }^{\ast }$
Output: all occurrences of $P$ in $T$

Algorithms

Brute-force Algorithm

Definition

Brute-force Algorithm (String Matching)

Given a text $T=t_1\dots t_n$ and a pattern $P=p_1\dots p_m$, the brute-force algorithm for the string matching problem tests every possible starting position. At each position, it compares pattern characters with text characters from left to right until a mismatch occurs or the whole pattern matches. It returns

$$\{i\in \{1,\dots ,n-m+1\}:\forall j\in \{1,\dots ,m\},t_{i+j-1}=p_j\}.$$

After each test, the starting position advances by one, so overlapping occurrences are retained. If $m>n$, there are no occurrences. The empty string occurs at all $n+1$ boundaries of the text.

Link to original