Метасимвол всего один — * (0 или более произвольных символов). Например, для a*a

a.*a

Ну да, в моем случае * — означает .*

В книгах «Практика программирования» (где про grep) и «Идеальный код» (первая глава) приводится реализация подмножества регулярных выражений объёмом в 35 строк. Я бы для начала переделал его (код одинаковый) под задачу и посмотрел на скорость. Если будет слишком медленно, то думать дальше (хотя при m * должно получиться в районе bigomega(N^m), т.е. не быстро в любом случае).

Тот код в 35 строк я, кажется, уже видел, когда искал что-то по теме. Можно попробовать просто удалять m встречающихся подряд * до одной. А как подобная задача обычно решается? Наверняка же реализованы уже хорошие методы для overlapping matches.

И если использовать тот код (если я правильно помню), то оно будет доходить только до первого совпадения, не считая еще того, что нужно будет проверить варианты для подстрок с началами во всех возможных местах (string.length).

а головой думать ?

тот самый случай когда универсальное решение(регулярки) проигрывают частному.

причем начало одинаково для всех: ищешь последний маркер и глядишь в очередь.

ps/ я бы на С написал, будь такая необходимость.

Из паттерна делаем строку с 2 нулями на конце, заменяем '*' нулем.
Ищем первый образец, от следующего за концом найденного символа ищем следующий образец. Повторяем, пока не закончится строка образцов.
Получив искомый фрагмент, сдвигаем начало поиска последнего (n-го) фрагмента образца на 1, повторяем, собирая совпавшее. Повторяем для n-1, n-2,.. фрагментов образца рекурсивно.

Можно попробовать просто удалять m встречающихся подряд * до одной.

Это да, но от a*b*c*d*e не спасёт (это вырожденный случай, конечно).

А как подобная задача обычно решается? Наверняка же реализованы уже хорошие методы для overlapping matches.

Вполне возможно, но мне описания подобных алгоритмов не встречались, поэтому не знаю стандартного решения.

И если использовать тот код (если я правильно помню), то оно будет доходить только до первого совпадения, не считая еще того, что нужно будет проверить варианты для подстрок с началами во всех возможных местах (string.length).

Всё так, но если убрать пару проверок, то он станет обходить все варианты. Надо просто продолжать искать до конца строки, даже если уже видели совпадение. И там вроде не жадный оператор * был, его надо научить идти дальше после успешного совпадения.

не помню откуда утащил

static int string_matchhere(char *regexp, char *text)
{
    if (!*regexp)
        return !*text;
    if (*regexp == '*')
        return string_matchstar(regexp + 1, text);
    if (!*text && *regexp == *text)
        return string_matchhere(regexp + 1, text + 1);
    return 0;
}

static int string_matchstar(char *regexp, char *text)
{
    do
        if (string_matchhere(regexp, text)) return 1;
    while (*text++);
    return 0;
}

static int string_match(char *regexp, char *text)
{
    if (regexp[0] == '^')
        return string_matchhere(regexp + 1, text);
    do
        if (string_matchhere(regexp, text)) return 1;
    while (!*text++);
    return 0;
}

Какие эффективные способы решения для этого существуют?

Добавлю к предложенным еще пару способов, с предварительной обработкой.

Если маска известна на этапе компиляции и нужно искать совпадения в разных строках, то можно генерировать код для матчинга. То есть сделать что-то типа re2c, только проще.

Если строка для поиска постоянна, а меняются только маски, можно попробовать матчить с помощью суффиксного массива. Он дает быстрый (log(N)) поиск подстроки (точнее поиск смещения подстроки в строке) + подстроки в нем отсортированы. Для строки 'ababa' и подстроки 'a' получим индексы 1, 3, 5, уже почти готовое решение.

можно написать скрипт с явной логикой

можно написать скрипт порождающий скрипт явной логики

вопрос только - зачем?

компилируй регулярку - потом обращайся с контекстом