METHODS AND APPARATUS FOR DETECTING PATTERNS IN A DATA STREAM

In some embodiments, a method includes generating a prefix trie for a set of patterns, generating a suffix trie for the set of patterns, and establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie. In some embodiments, a method includes adding a suffix to a suffix tree, so that the suffix (which is at least a portion of a pattern) is represented in the tree by a path that begins at a first node and ends at a second node, and associating with at least the first node and the second node a pattern identifier that identifies the pattern.