Find all (including overlapping) substrings matching a regular expression in Python

user_430083 0
Viewed 78

I need to find positions of all substrings matching a regular expression within a string. For instance, if the string is abbba and the regexp is (b|bb)(?=a), the result should be [(2, 4), (3, 4)].

What I’ve come up with is

def get_ranges(pattern: str, string: str) -> list[tuple[int, int]]:
    n = len(string)
    return [(start, end) for start in range(n + 1) for end in range(start, n + 1)
            if re.fullmatch(f'.{{{start}}}({pattern}).{{{n - end}}}', string)]

But this tends to perform extremely slowly, especially given that it doesn’t allow precompiled regexps to be used. Are there any more efficient ways to solve the problem?

python regex performance
2 Answers

First of all I think you should use for end in range(start, n + 1). For the end variable I don't see any reason to start ranging from 0 for every iteration. Just with this edit, executing this code

for i in range(300000):
    get_ranges(r"(b|bb)(?=a)", "abbba")

I pass from 9.67 to 6.01 secs.

user_46077330

You may want to try a slightly different regex - (b{1,2})(?=a) which should be slightly faster.

Secondly, you can compile the pattern and use it compiled by cutting the string and not the regex:

pattern = re.compile('(b{1,2})(?=a)')
def get_ranges(pattern: str, string: str):

result = []
start, end = 0, len(string)
match = pattern.search(string)
while match is not None and start < end:
    result.append((match.start(0)+start, match.end(0)+start))
    start += match.start(0) + 1
    match = pattern.search(string[start:])

return result

You can also yield instead of constructing result in its entirety before returning.

Timings for comparison (per 1 million execs):

  • original: 38.42 s
  • above: 2.14 s (17.95x speedup)
  • yield version: 0.2914 s (131.85x speedup)
user_65739020
Related