49
|
1 |
#!/usr/bin/env python
|
|
2 |
import re
|
|
3 |
import sys
|
|
4 |
|
558
|
5 |
# A case of catastrophic backtracking in Python
|
420
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
6 |
#
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
# regex: (a?){n} a{n}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
# strings: aa...
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
#
|
558
|
10 |
# call with:
|
|
11 |
#
|
|
12 |
# > ./catastrophic.py 20
|
|
13 |
#
|
|
14 |
# or
|
|
15 |
#
|
|
16 |
# > ./catastrophic.py 28
|
|
17 |
#
|
|
18 |
#
|
420
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
# call with timing as:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
#
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
# > time ./catastrophic.py 20
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
|
558
|
23 |
|
|
24 |
|
420
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
# counter n given on the command line
|
49
|
26 |
cn = sys.argv[1]
|
|
27 |
|
420
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
# constructing the regex
|
49
|
29 |
r1 = '((a?){%s})' % cn
|
|
30 |
r2 = 'a{%s}' % cn
|
|
31 |
|
420
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
# calling the matching function
|
49
|
33 |
m = re.match(r1 + r2 , "a" * int(cn))
|
|
34 |
|
|
35 |
print m.group(0)
|