# String matching

## Input

Two non-empty sequences, $S$ and $T$. Let $n(S),n(T) \in \mathbb{N}$ denote the lengths of $S$ and $T$, respectively.

## Output

A sorted sequences $P$ of positions of $S$, that is, $P[i] \in \{ 1,...,n(S)\}$ for all positions of $P$. More specifically, $P$ contains all positions $m$ of $S$ such that $S[m+j-1]=T[j]$ for all $j \in \{ 1,...,n(T)\}$. Such a subsequence $(S[m],...,S[m+n(T)-1])$ is called an occurrence of $T$ in $S$.

N/A

## Remark

Note that occurrences of $T$ in $S$ may overlap (otherwise, the string matching problem would be trivially solvable in linear time).