Cuozzo: /* Known algorithms */

2014-10-01T19:30:13Z

Known algorithms

← Older revision		Revision as of 19:30, 1 October 2014
Line 16:		Line 16:
	==Known algorithms==		==Known algorithms==
	[[Simple string matching algorithm]]		[[Simple string matching algorithm]]

	[[String matching based on finite automaton]]		[[String matching based on finite automaton]]

	==Remark==		==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).		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).

Cuozzo: Created page with "NOTOC Category:Checkup Category:Algorithmic Problem Category:Pattern Matching ==Input== Two non-empty sequences, $S$ and
2014-10-01T19:29:35Z

Created page with "NOTOC Category:Checkup Category:Algorithmic Problem Category:Pattern Matching ==Input== Two non-empty sequences, <math>S</math> and <mat..."

New page
NOTOC
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Pattern Matching]]
==Input==
Two non-empty [[Sets and sequences|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 [[Sets and sequences#Ordered and sorted sequences|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).