[–] tsuberim 8y ago ↗ Isn't it O(n) where n is the length of the string to match? Because you can compile any regex to a DFA and run it over the string. [–] mrzasa 8y ago ↗ Not sure what you mean. For detailed complexity analysis, please read this excellent post by Russ Cox: https://swtch.com/~rsc/regexp/regexp1.html
[–] mrzasa 8y ago ↗ Not sure what you mean. For detailed complexity analysis, please read this excellent post by Russ Cox: https://swtch.com/~rsc/regexp/regexp1.html
2 comments
[ 2.8 ms ] story [ 14.1 ms ] thread