some doubt: Is re2 really linear time ?

### 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 = cat ` matches the input text `S` , then some` s1 `matches `` and some `s2 `matches `` 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](https://github.com/google/re2):

* [Regular Expression Matching Can Be Simple And Fast](https://swtch.com/~rsc/regexp/regexp1.html)
introduced the classical NFA and DFA and the regular expression and their equivalence.
* [Regular Expression Matching: the Virtual Machine Approach](https://swtch.com/~rsc/regexp/regexp2.html)
recursion-traceback、 non-recursion (stack)-traceback、non-traceback implementations of machines to matches text
and **traceback**-recursion 、 non-recursion -**traceback** matchines to tell submatches.
* [Regular Expression Matching in the Wild](https://swtch.com/~rsc/regexp/regexp3.html)

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.