The Aho/Corasick String Matching Automaton

An Aho/Corasick String Matchin Automaton for a given finite set P of patterns is a (deterministic) finite automaton G accepting the set of all words containing a word of P as a suffix.

G consists of the following components:

  1. finite set Q of states
  2. finite alphabeth A
  3. transition function g: Q × A -> Q + {fail}
  4. failure function h: Q -> Q + {fail}
  5. initial state q0 in Q
  6. a set F of final states
Example: P = {ab, ba, babb, bb}


Aho/Corasick String Matching Automaton.