I have been trying to find approaches to locate sub-matches within an expression in O(n) (n being the length of the input) time myself.
I have a thought, which I would like to present here, and maybe I could get some help ironing it out.
Consider a regular expression: x(ab|(abc))y
In this case, we are interested in 2 submatch captures. The NFA and DFA for the RE above are:
We shall focus on the 2nd submatch capture for now, since it poses a greater problem than the first one. The reason that sub-match captures are problematic is because the generated DFA can share a prefix with another expression that is not part of the submatch capture. However, I believe that a DFA that is part of a submatch capture can not share a suffix with another DFA that is not part of the submatch capture that it is part of. (Except for examples such as (ab|(ab)), in which case it doesn't matter).
Keeping this in mind, it seems that it is sufficient to start tracking a capture when we reach a state in the DFA that is composed of a state in the original NFA but corresponds to an open parenthesis to start the submatch capture. For example, state 2 in the DFA is such a state. However, we shall tag exit edges instead of exit nodes since we want to avoid the ambiguity problem. We always tag those edges as interesting edges if the destination DFA state is composed of an NFA state that included a closing parenthesis.
For example, if we tag state 16 in the NFA as an interesting state, then we find that epsilon-closure(16) = (16, 8, 9), and that would correspond to state 6 in the DFA. However, we need to track those edges that are incident on node 6 in the DFA and also have a starting node that originates from some state within the parenthesized expression. Depending on how we generate the NFA from the RE, we can ensure that we never have to deal with this situation.
I believe that if we skip the DFA minimization step then the choice of such a starting node (and hence an edge) is easy to make. For example, consider the following RE: x(ab|(abc)|s)y
The NFA and DFA follow:
It would have been entirely possible for an edge to go from state 2 in the DFA to state 7 in the DFA on an input of 's', but because of our construction, this doesn't happen.
The good news seems to be that we can match subexpressions in linear time. However, the bad news seems to be that the number of states in our DFA will at least be exponential in the number of parenthesized subexpressions (since we prefer to branch and replicate everything after it).