String matching

Input

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

Output

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

Objective

N/A

Known algorithms

Simple string matching algorithm

String matching based on finite automaton

Remark

Note that occurrences of [math]\displaystyle{ T }[/math] in [math]\displaystyle{ S }[/math] may overlap (otherwise, the string matching problem would be trivially solvable in linear time).