3 ms·
Actually, the O(n^2) thing is correct for an NFA simulation that tracks states not paths. While there might be O(2^n) paths, there are n states you can be in at
by cyphar 11y ago
Actually, the O(n^2) thing is correct for an NFA simulation that tracks states not paths. While there might be O(2^n) paths, there are n states you can be in at any one point.
https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html