#!/usr/bin/env python+
−
import re+
−
import sys+
−
+
−
# case of catastrophic backtracking in Python+
−
#+
−
# regex: (a*)*b+
−
# strings: aa...a+
−
#+
−
# call with timing as:+
−
#+
−
#   time ./catastrophic.py 20+
−
+
−
# counter n given on the command line+
−
cn = sys.argv[1]+
−
+
−
# calling the matching function+
−
s = ("a" * int(cn))+
−
m = re.match('(a*)*b' , s) +
−
+
−
print s+
−
print m+
−