In the paper there are some bounds about the number of states in the automata as a function of the length of the input. So one could limit the length of the input when using back references to bound the complexity of the algorithm. They have used their algorithm for snort (network intrusion detection) using asic. The author could contact the authors of the paper and ask for (or pay for) an implementation.
By the way, good work ripgrep and rust.