CODEWITHSUNDEEP
regex
hello world
hello world

Reputation: 624

Regular expressions: search (instead of match) with DFA

I have been wondering about theory behind search mode of regex matcher. So, say I have a regex that matches aab, what if instead of match at the beginning of the string I wanna be able to perform this match starting from any position of the string. What I mean - in match mode I can only verify that string aab is consistent with a regex, on the other hand with search this should work with say aaab producing corresponding span result. So super specifically - is there any way to build DFA searcher, or this is fundamentally impossible since it would require additional memory which you cant have in DFSM. It is obvious though that you can in fact build searcher from matcher by reapplying matcher to input string in a for loop, but complexity of such approach is something like O(len_of_pattern * len_of_input).

Upvotes: 2

Views: 194

Answers (2)

jasonharper
jasonharper

Reputation: 9597

A regex searcher is basically the same thing as a regex matcher with .* tacked onto the front of the expression.

Upvotes: 2

Will Barnwell
Will Barnwell

Reputation: 4089

I think you basically answered your own question. Search, like many other features in modern regex implementations, leverages the wonder of memory to do things unfeasible with a Finite Automata. DFAs traditionally cannot loop over strings or backtrack along input as this would require memory. Search requires the ability to find a match and then understand how that match fits in the string.

Upvotes: 1

Related Questions