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."