My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the length of the regex pattern.
Consider this pathological example: $a^*a^*ab$, which should match at least one $a$ followed by exactly one $b$. I'm going to refer to the compiled NFA as having three parts, with a "front part" representing the first $a^*$, a "middle part" representing the second $a^*$, and a "back part" representing $ab$.
The front and middle parts would look like this, with a simple $a$ symbol transition for $N(s)$:
The back part would look like two of these symbol transitions, one for $a$ then one for $b$:
Let's try to match $aaab$:
- The compiled NFA starts in the start state.
- Having two options due to the first Kleene star, it splits execution. It doesn't matter which state goes where, so let's just say state #1 takes the epsilon transition to move on to the middle part, and state #2 stays in the front part.
- State #2 would match the first $a$, then split again. Let's say state #2 proceeds along the loop-back epsilon transition and stays in the front part, while a new state #3 moves on to the middle part. Now there are three states.
- Meanwhile, state #1 – now in the middle part – also splits due to the second Kleene star, and does basically the same thing as state #2 did in the front part. Let's say state #1 moves on again to the back part, while a new state #4 goes into the Kleene star construction in the middle part, matches the first $a$, and in turn splits again into a state #5 that loops back within the second Kleene star construction, so state #4 can move on to the back part like state #1 did, except that state #4 has already matched the first $a$.
At this point, you can probably see what I'm getting at; the first Kleene star causes execution to split, in the worst case, $O(n)$ times, where $n$ is the length of the input, then the second Kleene star potentially causes each of those $O(n)$ splits to split $O(n)$ times, resulting in $O(n^2)$.
So there must be some way of pruning the possible states and avoiding $O(n^2)$ splits. An obvious pruning strategy would be to prune states if we've already visited the same node before in another state which had already consumed exactly the same amount of the input string. Keeping track of how much input we've consumed at each state is important since we cannot greedily consume either as much or as little as possible in the Kleene star constructions; in the example above, the whole input is only matched if the front and middle parts consume only the first two $a$'s between the two of them, so the back part can get the third $a$ and the $b$. But, this pruning strategy would result in $O(nk)$ space and time complexity, where $k$ is the length of the regex pattern, since there are $O(k)$ nodes in the NFA, and each node can have a unique state depending on how much of the length-$n$ input string it's consumed. I'm ok with $O(nk)$ running time, but I'm concerned about $O(nk)$ space complexity for large inputs in my application.
Is there some more genius pruning strategy that I'm not aware of? I don't have access to ACM, so I'm not able to read the original paper, and none of the articles of read about it go into enough detail to untangle this kind of situation.