What's the Time Complexity of Average Regex algorithms?

regex algorithm complexity-theory
avgvstvs picture avgvstvs · May 5, 2011 · Viewed 35.6k times · Source

I'm not new to using regular expressions, and I understand the basic theory they're based on--finite state machines.

I'm not so good at algorithmic analysis though and don't understand how a regex compares to say, a basic linear search. I'm asking because on the surface it seems like a linear array search. (If the regex is simple.)

Where could I go to learn more about implementing a regex engine?

Answer

porges picture porges · May 5, 2011

This is one of the most popular outlines: Regular Expression Matching Can Be Simple And Fast . Running a DFA-compiled regular expression against a string is indeed O(n), but can require up to O(2^m) construction time/space (where m = regular expression size).

Related questions

.NET - How can you split a "caps" delimited string into an array?

How do I go from this string: "ThisIsMyCapsDelimitedString" ...to this string: "This Is My Caps Delimited String" Fewest lines of code in VB.net is preferred but C# is also welcome. Cheers!

Read More
When do we actually use a Trie?

I am starting to read about Trie. I got also references from friends here in: Tutorials on Trie I am not clear on the following: It seems that to go on and use a Trie one assumes that all the …

Read More
Efficiently querying one string against multiple regexes

Lets say that I have 10,000 regexes and one string and I want to find out if the string matches any of them and get all the matches. The trivial way to do it would be to just query the string …

Read More