Single String Search: Difference between revisions

Revision as of 07:52, 10 April 2023

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

$m$: pattern length

$n$: length of searchable text

$s$: size of the alphabet

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

@@ Line 26: / Line 26: @@
 | [[Naïve string-search algorithm (Single String Search String Search)|Naïve string-search algorithm]] || 1940 || $O(m(n-m+{1}))$ || $O({1})$ || Exact || Deterministic ||
 |-
-| [[Knuth-Morris-Pratt (KMP) algorithm (Single String Search String Search)|Knuth-Morris-Pratt (KMP) algorithm]] || 1977 || $O(m+n)$ || $O(m)$ || Exact || Deterministic || [https://pdfs.semanticscholar.org/4479/9559a1067e06b5a6bf052f8f10637707928f.pdf Time] & [https://www.semanticscholar.org/paper/Fast-Pattern-Matching-in-Strings-Knuth-Morris/5253fead88bfeaaa2930daccb7324a264cb681a9?p2df Space]
+| [[Knuth-Morris-Pratt (KMP) algorithm (Single String Search String Search)|Knuth-Morris-Pratt (KMP) algorithm]] || 1977 || $O(m+n)$ || $O(m)$ || Exact || Deterministic || [https://pdfs.semanticscholar.org/4479/9559a1067e06b5a6bf052f8f10637707928f.pdf Time & Space]
 |-
 | [[Boyer-Moore (BM) algorithm (Single String Search String Search)|Boyer-Moore (BM) algorithm]] || 1977 || $O(mn + s)$ || $O(s)$ || Exact || Deterministic || [https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf Time & Space]