What is the complexity of regular expression?

regex complexity-theory big-o
Ahmad Farid picture Ahmad Farid · Dec 7, 2010 · Viewed 34.3k times · Source

What is the complexity with respect to the string length that takes to perform a regular expression comparison on a string?

Answer

NPE picture NPE · Dec 7, 2010

The answer depends on what exactly you mean by "regular expressions." Classic regexes can be compiled into Deterministic Finite Automata that can match a string of length N in O(N) time. Certain extensions to the regex language change that for the worse.

You may find the following document of interest: Regular Expression Matching Can Be Simple And Fast.

Related questions

What's the Time Complexity of Average Regex algorithms?

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 …

Read More
A Regex that will never be matched by anything

This might sound like a stupid question, but I had a long talk with some of my fellow developers and it sounded like a fun thing to think of. So; what's your thought - what does a Regex look like, …

Read More
Regular expression to match a line that doesn't contain a word

I know it's possible to match a word and then reverse the matches using other tools (e.g. grep -v). However, is it possible to match lines that do not contain a specific word, e.g. hede, using a regular …

Read More