1 #!/usr/bin/env python

     2 import re

     3 import sys

     4 

     5 # case of catastrophic backtracking in Python

     6 #

     7 # regex: (a?){n} a{n}

     8 # strings: aa...

     9 #

    10 # call with timing as:

    11 #

    12 #   > time ./catastrophic.py 20

    13 

    14 # counter n given on the command line

    15 cn = sys.argv[1]

    16 

    17 # constructing the regex

    18 r1 = '((a?){%s})' % cn

    19 r2 = 'a{%s}' % cn

    20 

    21 # calling the matching function

    22 m = re.match(r1 + r2 , "a" * int(cn)) 

    23 

    24 print m.group(0)