3 ms·
Skimming over it, the implementation looks inefficient: int matchstar(int c, char *regexp, char *text) { do { /* a * matches zero or more in
by jstimpfle 7y ago
Skimming over it, the implementation looks inefficient:
int matchstar(int c, char *regexp, char *text)
{
do { /* a * matches zero or more instances */
if (matchhere(regexp, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
That can be used to match short strings, but not to grep through a filesystem. A good regex matcher has runtime O(N*M) where N is the length of the regex (typically very short) and M is the length of the scanned text.
- ufo 7y agoA surprising number of regex tools used in the wild employ a backtracking algorithm like this one. Some popular features such as lookaheada, lookbehinds, and backreferences can't always be matched using a finite automaton.
- user2994cb 7y agoAn FSA matcher will be O(M) - one state transition per input character.
- jstimpfle 7y agoIf you're looking at a specific regex (~FSA), then N is constant... If you have a function that runs an arbitrary regex, then N will vary.