#!/usr/bin/env python3+ −
+ −
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)+ −