Single String Search

Description

Single string search algorithms try to find a place where a string (also called a pattern) is found within a larger string or text.

Related Problems

Related: Multiple String Search

Parameters

$m$: pattern length

$n$: length of searchable text

$s$: size of the alphabet

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Naïve string-search algorithm	1940	$O(m(n-m+{1}))$	$O({1})$	Exact	Deterministic
Knuth-Morris-Pratt (KMP) algorithm	1977	$O(m+n)$	$O(m)$	Exact	Deterministic	Time & Space
Boyer-Moore (BM) algorithm	1977	$O(mn + s)$	$O(s)$	Exact	Deterministic	Time & Space
Rabin-Karp (RK) algorithm	1987	$O(mn)$	$O({1})$	Exact	Deterministic	Time
Bitap algorithm	1964	$O(mn)$	$O(m)$	Exact	Deterministic	Time
Tuned Boyer-Moore algorithm	1991	$O(mn)$	$O(m + s)$	Exact	Deterministic	Time & Space
Two-way String-Matching Algorithm	1991	$O(n + m)$	$O({1})$	Exact	Deterministic	Time & Space
String-Matching with Finite Automata	1940	$O(mn)$	$O(m)$	Exact	Deterministic
Quick-Skip Searching	2012	$O(mn)$	$O(m)$	Exact	Deterministic	Time
Fast Hybrid Algorithm	2017	$O(n+m)$+ $O(m+s)$	$O(m)$	Exact	Deterministic	Time
Backward Non-Deterministic DAWG Matching (BNDM)	1998	$O(n+m)$	$O(sm)$	Exact	Parallel	Time & Space
Boyer-Moore-Horspool (BMH)	1980	$O(mn + s)$	$O(s)$	Exact	Deterministic	Time
Raita Algorithm	1991	$O(mn + s)$	$O(s)$	Exact	Deterministic	Time
BOM (Backward Oracle Matching)	1999	$O(m)$ + $O(mn)$	$O(m)$	Exact	Deterministic	Time & Space
Apostolico–Giancarlo Algorithm	1986	$O(m + s)$ + $O(n)$	$O(m)$	Exact	Deterministic	Time & Space
Wu and Manber, Fuzzy String Matching	1992	$O(nk \lceil m/w \rceil)$	$O(ms + k \lceil m/w \rceil)$	Levensthein Distance = k	Deterministic	Time & Space

Time Complexity graph

Space Complexity graph

Pareto Decades graph