diff -r 4110ab35e5d8 -r 25bc57b32efa progs/catastrophic.py --- a/progs/catastrophic.py Wed Sep 14 16:51:04 2016 +0100 +++ b/progs/catastrophic.py Tue Sep 20 12:13:11 2016 +0100 @@ -2,11 +2,23 @@ import re import sys +# case of catastrophic backtracking in Python +# +# regex: (a?){n} a{n} +# strings: aa... +# +# call with timing as: +# +# > time ./catastrophic.py 20 + +# counter n given on the command line cn = sys.argv[1] +# constructing the regex r1 = '((a?){%s})' % cn r2 = 'a{%s}' % cn +# calling the matching function m = re.match(r1 + r2 , "a" * int(cn)) print m.group(0)