title: Find all (including overlapping) substrings matching a regular expression in Python
body: <p>I need to find positions of all substrings matching a regular expression within a string. For instance, if the string is <code>abbba</code> and the regexp is <code>(b|bb)(?=a)</code>, the result should be <code>[(2, 4), (3, 4)]</code>.</p>
  <p>What I’ve come up with is</p>
  <pre class="lang-py prettyprint-override"><code>def get_ranges(pattern: str, string: str) -&gt; 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)]
  </code></pre>
  <p>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?</p>