1. A method for submatch extraction, the method comprising: receiving an input string; receiving a regular expression; converting, by a processor, the regular expression including a capturing group into an ordered binary decision diagram (OBDD); processing the input string by the OBDD, one input string character at a time, wherein processing of an individual input string character comprises outputting a tag representing a capturing group that corresponds to the individual input string character; determining that the regular expression matches the input string; and in response to a determination that the regular expression matches the input string, extracting a submatch based on the OBDD by processing the tag and the input string in reverse order by the OBDD, one input string character at a time, wherein the submatch corresponds to a substring of the input string, and the substring corresponds to the capturing group.