One-dimensional string matching
Jump to navigation
Jump to search
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.