One-dimensional string matching

Input

Two ordered sequences, [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n=|S| }[/math] and [math]\displaystyle{ T }[/math] of length [math]\displaystyle{ m=|T| }[/math].

Output

A sorted sequence [math]\displaystyle{ R }[/math] of integral values from [math]\displaystyle{ \{ 1,...,n\} }[/math] such that [math]\displaystyle{ i \in R }[/math] if, and only if, it is [math]\displaystyle{ i\le n-m+1 }[/math] and [math]\displaystyle{ T[j]=S[i+j-1] }[/math] for all [math]\displaystyle{ j \in \{ 1,...,m \} }[/math].

Objective

N/A

Complexity

Polynomial.

Known algorithms

1. Simple string matching algorithm
2. String matching based on finite automaton