Worst-case time complexity?

Create issue
Issue #281 wontfix
Former user created an issue

The regex module is excellent and fast. However, it supports features (like back-references) that cannot be implemented using linear-time algorithms.

I've only glanced at the code, but it doesn't appear to be using a Thompson-style implementation.

My question, then, is: if a given expression doesn't use back-references, fuzzy matching, etc, is performance guaranteed to be linear in the length of the input string for all possible inputs? Or are there some inputs that cause exponential-time behavior?

Thank you.

Comments (1)

  1. Matthew Barnett repo owner

    It uses backtracking, but it has extra checks to reduce the chance of catastrophic backtracking. Its performance is not guaranteed to be linear, and I'm not going to add an alternative implementation, e.g. Thompson, because there's enough code in the module as it is!

  2. Log in to comment