Aho-Corasick String
Matching
An Ecient String Matching
Introduction
Locate all occurrences of any of a
nite number of keywords in a string
of text.
Consists of constructing a nite state
pattern matching machine from the
keywords and then using the pattern
matching machine to process the
text string in a single pass.
Pattern Matching
Machine(1)
Let be a nite set of
strings which we shall call keywords
and let x be an arbitrary string which
we shall call the text string.
The behavior of the pattern matching
machine is dictated by three functions:
a goto function g , a failure function f ,
and an output function output.
yyy
K
k
,,,
21
Pattern Matching
Machine(2)
Goto function g ： maps a pair
consisting of a state and an input
symbol into a state or the message fail.
Failure function f ： maps a state into a
state, and is consulted whenever the
goto function reports fail.
Output function ： associating a set of
keyword (possibly empty) with every
state.
