> How idempotence has to do with anything? A regex match is supposed to return a result, not perform effects…

Correct, which is why I was asking why the GP wrote:

> I'm unable to see how the approach suggested in the paper could be made idempotent with Perl's regular expression engine while still maintaining linear performance.