| author | Christian Urban <christian.urban@kcl.ac.uk> |
| Mon, 17 Aug 2020 17:42:37 +0100 | |
| changeset 744 | a33ce6c8e2c3 |
| parent 742 | 155426396b5f |
| child 745 | 905b60a029bf |
| permissions | -rwxr-xr-x |
| 49 | 1 |
#!/usr/bin/env python |
2 |
import re |
|
3 |
import sys |
|
4 |
||
| 613 | 5 |
# case of catastrophic backtracking in Python |
| 558 | 6 |
# |
| 613 | 7 |
# regex: (a*)*b |
8 |
# strings: aa...a |
|
| 558 | 9 |
# |
|
420
25bc57b32efa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
411
diff
changeset
|
10 |
# call with timing as: |
|
25bc57b32efa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
411
diff
changeset
|
11 |
# |
| 742 | 12 |
# time ./catastrophic.py 20 |
|
420
25bc57b32efa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
411
diff
changeset
|
13 |
|
|
25bc57b32efa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
411
diff
changeset
|
14 |
# counter n given on the command line |
| 49 | 15 |
cn = sys.argv[1] |
16 |
||
| 613 | 17 |
# calling the matching function |
18 |
s = ("a" * int(cn))
|
|
19 |
m = re.match('(a*)*b' , s)
|
|
| 49 | 20 |
|
| 613 | 21 |
print s |
| 701 | 22 |
print m |