Multiple String Search: Difference between revisions

Revision as of 14:42, 15 February 2023

Multiple string search algorithms try to find a place where one or several strings (also called patterns) are found within a larger string or text.

$m$: longest pattern length

$n$: length of searchable text

$s$: size of the alphabet

$k$: number of patterns to search for

$z$: number of matches

Name	Year	Time	Space	Approximation Factor	Model	Reference
Commentz-Walter Algorithm	1979	$O(mn)$	$O(km)$	Exact	Deterministic	Time
Aho–Corasick (AC) Algorithm	1975	$O(n + m + z)$	$O(km)$	Exact	Deterministic	Time
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 44: / Line 44: @@
 [[File:String Search - Multiple String Search - Space.png|1000px]]
-== Space-Time Tradeoff Improvements ==
+== Time-Space Tradeoff ==
 [[File:String Search - Multiple String Search - Pareto Frontier.png|1000px]]