FYI the title stated in the github readme itself is misleading and incomplete.. in the fine print clarifies that this is in polynomial time "in the size of the input text for a fixed number of backreferences in the pattern."
Is that somehow special? CFG parsing is O(n^3) worst case using Earley's algorithm, regexp is faster. Back-references is a matter of inserting extra non-terminals. I once wrote a regexp to DFA with backreferences. I never checked the correctness, though.