| author | Christian Urban <urbanc@in.tum.de> |
| Fri, 24 Nov 2017 03:10:23 +0000 | |
| changeset 155 | 371acb50643d |
| child 156 | cc6d036401f4 |
| permissions | -rw-r--r-- |
| 155 | 1 |
#!/usr/bin/env python |
2 |
import re |
|
3 |
import sys |
|
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 |
|
15 |
cn = sys.argv[1] |
|
16 |
||
17 |
# constructing the regex |
|
18 |
r1 = '((a?){%s})' % cn
|
|
19 |
r2 = 'a{%s}' % cn
|
|
20 |
||
21 |
# calling the matching function |
|
22 |
m = re.match(r1 + r2 , "a" * int(cn)) |
|
23 |
||
24 |
print m.group(0) |