Methods and apparatus for performing content inspection across packet boundaries using stateful packet content matching mechanisms. Pattern data structures are employed to facilitate string search algorithm machines. Incoming packets are classified to flows, and stored in corresponding flow queues. Flow table entries are used to identify the pattern data structure for a given flow. During content inspection, the algorithm machine updates state information to identify partial or full matches. When a partial match is detected towards the end of an earlier packet state information in the flow table is updated to reflect the state such that content inspection of a following packet begins at that state. As a result, content inspection across packet boundaries is supported. The techniques may further be employed in a packet processing context pipeline stage.