One-dimensional string matching

From Algowiki
Revision as of 09:22, 29 April 2015 by Weihe (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.

Known algorithms

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