Exact Set Matching Problem
In the exact set matching problem we locate occurrences
of any pattern of a set P = {P
1
, . . . , P
k
}, in target T [1 . . . m]
Let n =
P
k
i=1
|P
i
|. Exact set matching can be solved in time
O(|P
1
| + m + · · · + |P
k
| + m) = O(n + km)
by applying any linear-time exact matching k times
Aho-Corasick algorithm (AC) is a classic solution to
exact set matching. It works in time O(n + m + z), where z
is number of pattern occurrences in T
(Main reference here [Aho and Corasick, 1975])
AC is based on a refinement of a keyword tree
BSA Lecture 4: Aho-Corasick matching – p.2/24
