1 #!/usr/bin/env python

     2 import re

     3 import sys

     4 

     5 # case of catastrophic backtracking in Python

     6 #

     7 # regex: (a*)*b

     8 # strings: aa...a

     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 # calling the matching function

    18 m = re.match('(a*)*b' , "a" * int(cn)) 

    19 

    20 print m.group(0)