Lessons · Regex · a quantifier inside a quantifier

A quantifier inside a quantifier

(a+)+b lets the same characters be divided between the repetitions in many ways, and on a string that does not match, the engine tries all of them.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

This is a denial-of-service bug, not a slow line. The work doubles for every character added, so twenty is fine and thirty is a hung process.

Look for a quantified group whose contents are themselves quantified. Nearly every one has a flat equivalent that matches exactly the same strings.

re.search(r'(a+)+b', 'aaab').group()

It matches fine; the trouble is only ever on the strings that do NOT.

re.search(r'a+b', 'aaab').group()

The flat version, same answer.

re.search(r'a+b', 'aaa')

And this one gives up immediately, where the nested one would not.

Write the flat version of (a+)+b.

ab

It passes every test you write, because the tests are strings that match. The failure lives entirely in the ones that do not.

Practise a quantifier inside a quantifier on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.