A method for submatch extraction may include receiving an input string, receiving a regular expression, and converting the regular expression with capturing groups into a plurality of finite automata to extract submatches. The method further includes using a first automaton to determine whether the input string is in a language described by the regular expression, and to process the input string, and using states of the first automaton in a second automaton to extract the submatches. In addition, input partitioning and automaton minimization techniques may be employed to reduce the storage area consumed by the plurality of finite automata.