progs/catastrophic.py
changeset 420 25bc57b32efa
parent 411 1aec0e1fda86
child 558 447ed6c7cdad
equal deleted inserted replaced
419:4110ab35e5d8 420:25bc57b32efa
     1 #!/usr/bin/env python
     1 #!/usr/bin/env python
     2 import re
     2 import re
     3 import sys
     3 import sys
     4 
     4 
       
     5 # case of catastrophic backtracking in Python
       
     6 #
       
     7 # regex: (a?){n} a{n}
       
     8 # strings: aa...
       
     9 #
       
    10 # call with timing as:
       
    11 #
       
    12 #   > time ./catastrophic.py 20
       
    13 
       
    14 # counter n given on the command line
     5 cn = sys.argv[1]
    15 cn = sys.argv[1]
     6 
    16 
       
    17 # constructing the regex
     7 r1 = '((a?){%s})' % cn
    18 r1 = '((a?){%s})' % cn
     8 r2 = 'a{%s}' % cn
    19 r2 = 'a{%s}' % cn
     9 
    20 
       
    21 # calling the matching function
    10 m = re.match(r1 + r2 , "a" * int(cn)) 
    22 m = re.match(r1 + r2 , "a" * int(cn)) 
    11 
    23 
    12 print m.group(0)
    24 print m.group(0)