Attempting polynomial with respect to the string being searched for a constant regex is interesting. A finite regex will contain a finite number of back referen

Attempting polynomial with respect to the string being searched for a constant regex is interesting. A finite regex will contain a finite number of back references. I think a finite number of back references implies a maximum stack use for the backtracking approach. DFA plus finite size stack machine is convertible to a DFA with a smaller stack and onwards to a pure DFA. That is probably worth trying to implement, thank you for the push.