[mikhailfranco]

You could implement the NFA directly with concurrent exploration of all paths:

https://github.com/mike-french/myrex