String matching

From Algowiki
Jump to: navigation, search

Input

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

Output

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

Objective

N/A

Complexity

Known algorithms

Simple string matching algorithm

String matching based on finite automaton

Remark

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