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


/*****************/
/* trie matching */
/*****************/

/* n = length of text */

FOR i = 1 TO n
  q = root
  j = 1
  WHILE g(q, text[i+j-1] != null
    q = g(q, text[i+j-1])
    IF isElement(q, final)
      RETURN TRUE
    ENDIF
    j = j + 1
  ENDWHILE
ENDFOR