#!/usr/bin/env python

import re

import sys

# A case of catastrophic backtracking in Python

#

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

# strings: aa...

#

# call with:

#

#   > ./catastrophic.py 20

#

# or

#

#   > ./catastrophic.py 28

#

#

# 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)