From looking at the source code, Go's regexp package uses O(n) NFA-based matching, as described here: http://swtch.com/~rsc/regexp/regexp2.html http://swtch.co

From looking at the source code, Go's regexp package uses O(n) NFA-based matching, as described here: http://swtch.com/~rsc/regexp/regexp2.html http://swtch.com/~rsc/regexp/regexp2.html It isn't nearly as highly optimized as RE2, but it works in a similar way.