finditer hangs when matching against long string

Question

I have a somewhat complex regular expression which I'm trying to match against a long string (65,535 characters). I'm looking for multiple occurrences of the re in the string, and so am using finditer. It works, but for some reason it hangs after identifying the first few occurrences. Does anyone know why this might be? Here's the code snippet:

pattern = "(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)"

matches = re.finditer(pattern, string)
for match in matches:
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())

It prints out the first four occurrences, but then it hangs. When I kill it using Ctrl-C, it tells me it was killed in the iterator:

Traceback (most recent call last):
  File "code.py", line 133, in <module>
    main(sys.argv[1:])
  File "code.py", line 106, in main
    for match in matches:
KeyboardInterrupt

If I try it with a simpler re, it works fine.

I'm running this on python 2.5.4 running on Cygwin on Windows XP.

I managed to get it to hang with a very much shorter string. With this 50 character string, it never returned after about 5 minutes:

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

With this 39 character string it took about 15 seconds to return (and display no matches):

ddddddeddbedddbdddddddddddddddddddddddd

And with this string it returns instantly:

ddddddeddbedddbdddddddddddddd

Answer 1

Definitely exponential behaviour. You've got so many d* parts to your regexp that it'll be backtracking like crazy when it gets to the long string of d's, but fails to match something earlier. You need to rethink the regexp, so it has less possible paths to try.

In particular I think:

([ef]d\*b|d\*)*</pre></code> and <code><pre>([ef]|([gh]d\*(ad\*[gh]d)\*b))d\*b

Might need rethinking, as they'll force a retry of the alternate match. Plus they also overlap in terms of what they match. They'd both match edb for example, but if one fails and tries to backtrack the other part will probably have the same behaviour.

So in short try not to use the | if you can and try to make sure the patterns don't overlap where possible.