Wildcards

Для (*,?) есть очевидный алгоритм с динамическим программированием за

O(len str * len pattern)

Пусть F[i,j] - функция равная true если начальный префикс длиной i, соответствует начальному префиксу длины j из шаблона. Нужно аккурантно выразить F[i,j] через F[i-1,j-1],F[i-1,j], F[i,j-1] c учотом граничных условий и заполнить массив

Для общих регексвов можно построить за возможно экпонтенциальное время конечный автомам а затем ла линейное проверить соответствие, либо попытаться решать динамическим программированием (получится полином от размера str и шаблона).

А еще есть готовые библиотеки.

видимо man 3 fnmatch

int fnmatch(const char *pattern, const char *string, int flags);

The fnmatch() function checks whether the string argument matches the pattern argument, which is a shell wildcard pattern.