The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup.
However, for my purpose I need to know which paths the NFA went through for accepted words. This is obviously not trivial if I simply use the subset construction method. The NFA could also have $\epsilon$ transitions.
Of course, any such simulation could have a bad worst-case, in which there are a humongous amount of ways that the automaton could accept a given word. However, it'd be nice to have some sort of algorithm that runs, in, say, $O(m+n)$ for a word of length $m$ that the NFA has $n$ ways of accepting.
Is there any efficient way to do this?