Methods and systems are provided for using incremental operation for processing regular expressions in intrusion-prevention systems. In an embodiment, a state-transition table is provided, said table representative of a predetermined data pattern, and including states each having one or more egress events defining transitions to other states. A first portion of a subject is received, where the subject is to be evaluated for the presence of the predetermined data pattern. While using the state-transition table for said evaluation, a first state is transitioned into, after which it is determined that a set of restart information should be saved for the first state, said determination including identifying a tail to save from an end of the first portion of the subject. The restart information is saved, along with at least the identified tail.