Algorithm: Trie Matching

/***************************/
/* computation of the trie */
/***************************/

/* m[p] = lenght of pat[p] */
/* #pat = number of patterns */
/* g(Node, Character) is the transition function */
 
final = empty set
FOR p = 1 TO #pat
  q = root
  FOR j = 1 TO m[p]
    IF g(q, pat[p][j]) == null
      insert(q, pat[p][j])
    ENDIF
    q = g(q, pat[p][j])
  ENDFOR
  final = union(final, q)
ENDFOR


/***************************************/
/* computation of the failure function */
/***************************************/

/* h(Node) is the failure function */

h(root) = fail
FORALL {q' | parent(q') == root}
  h(q') = root
ENDFOR

FORALL {q' | depth(q')>1} in BFS order
  q = parent(q')
  c = the symbol with g(q,c) == q'
  r = h(q)
  WHILE r != fail AND g(r,c) == fail
    r = h(r)
  ENDWHILE
  IF r == fail
    h(q') = g(root,c)
  ELSE
    h(q') = g(r,c)
    IF isElement(h(q'), final)
      final = union(final, q')
    ENDIF
  ENDIF
ENDFOR


/****************/
/* Aho/Corasick */
/****************/

/* n = length of text */

q = root
FOR i = 1 TO n
  WHILE q != fail AND g(q, text[i]) == fail
    q = h(q)
  ENDWHILE
  IF q == fail
    q = root
  ELSE
    q = g(q, text[i])
  ENDIF
  IF isElement(q, final)
    RETURN TRUE
  ENDIF
ENDFOR
RETURN FALSE