1. A method for submatch extraction, the method comprising: receiving an input string; receiving a regular expression; and converting, by a processor, the regular expression with capturing groups into a plurality of finite automata to extract submatches, wherein the extracting 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.