In one embodiment, a method includes sampling text in a received packet at a network device and analyzing the sampled text using a sampled deterministic finite automata (DFA) to identify matches between a set of regular expressions and the text. The sampled DFA is created with the regular expressions sampled at a sampling rate calculated for the regular expressions using operations including selecting a minimum sampling rate from sampling rates computed for each of the regular expressions based on a minimum length of the text that can match the regular expression. An apparatus and logic are also disclosed herein.