Multiple String Search (String Search)

Description

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