1. A method comprising: in a processor of a security appliance coupled to a network: walking an input of a sequence of characters through a finite automata graph generated for at least one given pattern; and at a marked node of the finite automata graph: if a specific type of the at least one given pattern is matched at the marked node, processing the input sequence of characters through a reverse non-deterministic finite automata (rNFA) graph generated for the specific type of the at least one given pattern by walking the input sequence of characters backwards through the rNFA beginning from an offset of the input sequence of characters associated with the marked node.