Multiple String Search (String Search)

From Algorithm Wiki
Jump to navigation Jump to search


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.

Related Problems

Related: Single String Search


$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

Table of Algorithms

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

Time Complexity Graph

String Search - Multiple String Search - Time.png