The article offers a simple solution here: if the regex fits the model (no backtracking, no arbitrary code, etc..._), use the linear-scaling algorithm described. Else, use the slow, exponential one. Perl (according to the article) is not doing this.