Good prompt for a beautiful matcher with better complexity. Have a favorite?
https://www.oilshell.org/archive/Thompson-1968.pdf is longer and doesn't quite fix the problem (see third-to-last paragraph) but it is interesting and very tight.
https://www.oilshell.org/archive/Thompson-1968.pdf is longer and doesn't quite fix the problem (see third-to-last paragraph) but it is interesting and very tight.
#include <stdlib.h>
#include <string.h>
int match(char* regex, char* text) {
int n = strlen(regex);
char* active = calloc(n + 1, 1);
char* next_active = calloc(n + 1, 1);
active[0] = 1;
int found = 0;
int anchor = regex[0] == '^';
regex += anchor;
do {
for (int i = 0; i <= n; i++) {
if (!active[i])
continue;
if (regex[i] == '\0') {
found = 1;
goto DONE;
} else if (regex[i + 1] == '*') {
next_active[i + 2] = 1;
if (regex[i] == '.' || regex[i] == *text)
next_active[i] = 1;
} else if (regex[i] == '$' && regex[i + 1] == '\0') {
found = *text == '\0';
goto DONE;
} else {
next_active[i + 1] = regex[i] == *text;
}
}
char* tmp = next_active;
next_active = active;
active = tmp;
active[0] = !anchor;
memset(next_active, 0, n + 1);
} while (*text++ != '\0');
DONE:;
free(active);
free(next_active);
return found;
}Here's my favorite approach to "rediscovering" efficient regex matching: https://semantic-domain.blogspot.com/2013/11/antimirov-deriv... It's implicit in the Thompson paper I linked above, but imo not obvious from it.