Background
it's well-known that a NFA of M states spend O(MN) time when run on a N long text (shift M states on each step facing a token, and N steps in total) . And then it can be told whether the text is matched, true if the terminal state is reached or false otherwise.
Question
but what about the case of "tell the submatches" ( for example if a pattern P =<p1> cat <p2> matches the input text S , then somes1matches <p1> and some s2 matches <p2> and S = s1 cat s2, and we want to know what s1 is, one possible value is enough)。 Is re2 linear time to tell submatches ?
Attempts
I have viewed these three articles from mainpage of C++ version re2:
production implementation and several questions and according thoughts , one of the questions is what i concerned with : Does this regexp match this string? If so, where? Where are the submatches?, but i haven't seen any linear solution proposed under this quesion yet, only talks about the one-pass regex case, in which only one state on going when NFA running.
Background
it's well-known that a NFA of M states spend O(MN) time when run on a N long text (shift M states on each step facing a token, and N steps in total) . And then it can be told whether the text is matched, true if the terminal state is reached or false otherwise.
Question
but what about the case of "tell the submatches" ( for example if a pattern
P =<p1> cat <p2>matches the input textS, then somes1matches<p1>and somes2matches<p2>andS = s1 cat s2, and we want to know what s1 is, one possible value is enough)。 Is re2 linear time to tell submatches ?Attempts
I have viewed these three articles from mainpage of C++ version re2:
introduced the classical NFA and DFA and the regular expression and their equivalence.
recursion-traceback、 non-recursion (stack)-traceback、non-traceback implementations of machines to matches text
and traceback-recursion 、 non-recursion -traceback matchines to tell submatches.
production implementation and several questions and according thoughts , one of the questions is what i concerned with :
Does this regexp match this string? If so, where? Where are the submatches?, but i haven't seen any linear solution proposed under this quesion yet, only talks about the one-pass regex case, in which only one state on going when NFA running.