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 r = '(.*)a(.{%s})bc' % cn

    19 

    20 # calling the matching function

    21 #m = re.match(r, "axaybzbc") 

    22 m = re.match(r, "a" * 100 + "a" * int(cn) + "bc") 

    23 

    24 print m.group(0)