#!/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)+
−