Search code examples
pythonregexnon-greedy

Non-greedy in Python Regex

I try to understand the non-greedy regex in python, but I don't understand why the following examples have this results:

print(re.search('a??b','aaab').group())
ab
print(re.search('a*?b','aaab').group())
aaab

I thought it would be 'b' for the first and 'ab' for the second. Can anyone explain that?

Solution

  • This happens because the matches you are asking match afterwards. If you try to follow how the matching for a??b happens from left to right you'll see something like this:

    • Try 0 a plus b vs aaab: no match (b != a)
    • Try 1 a plus b vs aaab : no match (ab != aa)
    • Try 0 a plus b vs aab: no match (b != a) (match position moved to the right by one)
    • Try 1 a plus b vs aab : no match (ab != aa)
    • Try 0 a plus b vs ab: no match (b != a) (match position moved to the right by one)
    • Try 1 a plus b vs ab : match (ab == ab)

    Similarly for *?.

    The fact is that the search function returns the leftmost match. Using ?? and *? changes only the behaviour to prefer the shortest leftmost match but it will not return a shorter match that starts at the right of an already found match.

    Also note that the re module doesn't return overlapping matches, so even using findall or finditer you will not be able to find the two matches you are looking for.