equal
deleted
inserted
replaced
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) |