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