Efficient simulation of an NFA, while preserving the paths to the accept states
There is no need to construct the DFA. Instead, you can construct a dynamic programming table which answers the question "the NFA could be at state $s$ after reading the $k$th prefix of the word" (the parameters are both $s$ and $k$). In order to efficiently fill this table in the presence of $\epsilon$-transitions, you need to compute ahead of time the transitive closure of the $\epsilon$-transitions. As you fill the table, you can include data that will allow you to reconstruct at least some of the accepting paths (or all of them, if you insist, though it will be more tricky to handle the $\epsilon$-transitions). The running time, however, won't be linear but more like $O(q^2m)$, where $q$ is the number of states; perhaps you could optimize this further for sparse NFAs, but probably not to $O(m+n)$.