One-dimensional string matching: Difference between revisions

From Algowiki
Jump to navigation Jump to search
mNo edit summary
No edit summary
 
Line 4: Line 4:
__NOTOC__
__NOTOC__
==Input==
==Input==
Two [[Linear sequence|linear sequences]], <math>S</math> of length <math>n=|S|</math> and <math>T</math> of length <math>m=|T|</math>.
Two [[Sets_and_sequences#Ordered_and_sorted_sequences|ordered sequences]], <math>S</math> of length <math>n=|S|</math> and <math>T</math> of length <math>m=|T|</math>.


==Output==
==Output==

Latest revision as of 09:22, 29 April 2015


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