One-dimensional string matching

From Algowiki
Jump to: navigation, search


Input

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

Output

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

Objective

N/A

Complexity

Polynomial.

Known algorithms

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