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 # A 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 # |
|
10 # call with: |
|
11 # |
|
12 # > ./catastrophic.py 20 |
|
13 # |
|
14 # or |
|
15 # |
|
16 # > ./catastrophic.py 28 |
|
17 # |
|
18 # |
9 # |
19 # call with timing as: |
10 # call with timing as: |
20 # |
11 # |
21 # > time ./catastrophic.py 20 |
12 # > time ./catastrophic.py 20 |
22 |
13 |
23 |
|
24 |
|
25 # counter n given on the command line |
14 # counter n given on the command line |
26 cn = sys.argv[1] |
15 cn = sys.argv[1] |
27 |
16 |
28 # constructing the regex |
17 # calling the matching function |
29 r1 = '((a?){%s})' % cn |
18 s = ("a" * int(cn)) |
30 r2 = 'a{%s}' % cn |
19 m = re.match('(a*)*b' , s) |
31 |
20 |
32 # calling the matching function |
21 print s |
33 m = re.match(r1 + r2 , "a" * int(cn)) |
|
34 |
|
35 print m.group(0) |
|