String Matching Problem

computation

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 }$

Examples

$T=\text{ababc},P=\text{ab}$

$P$ occurs at indices $0$ and $2$.

$T=\text{aaaa},P=\text{aa}$

$P$ occurs at indices $0$, $1$, and $2$. Occurrences may overlap.

$T=\text{hello},P=\text{world}$

$P$ does not occur in $T$. The set of occurrences is empty.
Output: all occurrences of $P$ in $T$