#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>

static bool        
is_match(const char *restrict patt, const char *restrict str);

typedef struct Testdata{
    char    *p, *str;
    bool    matched;
} Testdata;

// Search if s is matched to pattern p
int                main(int argc, char *argv[]){
    bool real_mode = argc  != 1;     // true if real mode, false if test mode
    
    if (real_mode && argc < 3){
        fprintf(stderr, "Usage: %s 'string' 'pattern'\n", *argv);
        return 1;
    }
    
    if (real_mode){
        if (is_match(argv[2], argv[1]))
            printf("Lines matched!\n");
        else 
            printf("Line not matched\n");
        return 0;
    } else {
        Testdata dt[] = (Testdata[]) {
            [0].p = "abcde",        [0].str = "abcde",                          [0].matched = true
          , [1].p = "abcd?",        [1].str = "abcde",                          [1].matched = true
          , [2].p = "abcd?d",       [2].str = "abcde",                          [2].matched = false
          , [3].p = "*",            [3].str = "abcde",                          [3].matched = true
          , [4].p = "abc*xy",       [4].str = "abcqwewweqewqeqeeqeeeqxy",       [4].matched = true
          , [5].p = "abc*xy",       [5].str = "abc11111111xf22222xb33333xy",    [5].matched = true
          , [6].p = "abc*xy",       [6].str = "abcxyz",                         [6].matched = false
          , [7].p = "abc*xy*xz",    [7].str = "abcxy1111z11x11x222x22xz",       [7].matched = true
          , [8].p = "abc*xy*xz",    [8].str = "abcxy1111z11x11x222x22x",       [8].matched = false
          , [9].p = "abc*xy*xz*",   [9].str = "abcxy1111z11x11x222x22xzppppp",  [9].matched = true
        };
        int     failed = 0, total = sizeof dt/sizeof(Testdata);
        for (int i = 0; i < total; i++)
            if (is_match(dt[i].p, dt[i].str) != dt[i].matched){
                printf("Failed (%d): [%s] [%s] must be %s\n", i, dt[i].p, dt[i].str, dt[i].matched?"matched": "not matched");
                failed++;
            }
        printf("Total tests %d, failed %d\n", total, failed);
        return failed == 0;
    }
}

// end of substring 
static inline bool 
is_end(char c){
    return c == '\0' || c == '*';
}


// returns pos of not-match sym (or last pos of substring if matched)
// s1 - pattern side
static int         
is_submatch(const char *restrict s1, const char *restrict s2, bool *restrict matched){
    int     i = 0;
    while (!is_end(s1[i]) && 
           s2[i] != '\0'  && 
           (s1[i] == s2[i] || s1[i] == '?')    // only s1 has pattern ability
          )
        i++;
    if (matched){
        if (is_end(s1[i]) 
            // && s2[i] == '\0'
           )
            *matched = true;
        else
            *matched = false;
    }
    return i;
}

// skip str till symbol n of till the end of line
static int          
skip_to(const char *str, char c){
    int     i = 0;
    while (str[i] && str[i] != c)
        i++; 
    return i;
}

               //   abc*az
               //   abcdddddaxtttttaz

// assumption: patt and str has at lease 1 sym
static bool         
is_match(const char *restrict patt, const char *restrict str){
   int     i = is_submatch(patt, str, 0);
   patt += i;  str += i;
   while (*patt == '*') {
        while (*patt == '*')
            patt++;
        char next = *patt;      // even if '\0'
        bool matched = false;
        do {
            i = 0;      // to avoid confustion with prev run
            str += skip_to(str, next);
            if (*str == '\0')
                break;
            i = is_submatch(patt, str, &matched);
            if (!matched)
                str++;  // go to next symbol
        } while (!matched);
        patt += i; str += i;    
    };
    if (*str != '\0' || *patt != '\0')
        return false;
    else
        return true;
}

?

Тема называется так.
Если есть модеры, поправьте пожалуйста.

?

Здравствуйте, Nick-77, Вы писали:

N7>?

Красивая простыня, а где сабж? Нам её надо всю вычитывать, или таки можно привести короткий код по существу?

Здравствуйте, cures, Вы писали:

C>Здравствуйте, Nick-77, Вы писали:

N7>>?

C>Красивая простыня, а где сабж? Нам её надо всю вычитывать, или таки можно привести короткий код по существу?


is_match функция

Здравствуйте, Nick-77, Вы писали:

N7>is_match функция

А, ну если покритиковать — это можно. Только Вы бы хоть в исходный пост это добавили, раз уж тему без модеров не поменять.
Технический момент: если всё прошло хорошо, то неплохо бы возвращать успех, а не фэйл, иначе смысл юнит-теста теряется, то есть поменять на return failed != 0;
Стратегический момент: оно будет работать за произведение длин шаблона и строки, почему бы для каждого подфрагмента не сделать что-то типа КМП-разборщика, ведь наверное для того оно и задавалось? Или это Вы для себя делаете?
Ещё один тонкий момент: Вам нужно проверить точное совпадение, или частичное совпадение начиная с начала строки? Если первое — то оно так работать не будет, ну найдёте Вы короткий матч, а как узнать из этого, можно ли сматчить всю строку? Тогда, наверное, придётся таки преобразовывать NFA в DFA и честно по нему идти.
Ещё более технический момент: такое задание структуры у меня только чистый Ц понял, и то заорал, что неконстантный массив, пришлось статиком делать. Лучше бы попроще, поуниверсальней.

Здравствуйте, cures, Вы писали:

C>Здравствуйте, Nick-77, Вы писали:

N7>>is_match функция

C>А, ну если покритиковать — это можно. Только Вы бы хоть в исходный пост это добавили, раз уж тему без модеров не поменять.

да там и сообщение не меняется... или только у меня прав нет?

C>Технический момент: если всё прошло хорошо, то неплохо бы возвращать успех, а не фэйл, иначе смысл юнит-теста теряется, то есть поменять на return failed != 0;

ок, принято

C>Стратегический момент: оно будет работать за произведение длин шаблона и строки, почему бы для каждого подфрагмента не сделать что-то типа КМП-разборщика, ведь наверное для того оно и задавалось? Или это Вы для себя делаете?

я ж нуб, учусь типа... хочу регэксп реализовать полноценный. КМП разборщик это что?

C>Ещё один тонкий момент: Вам нужно проверить точное совпадение, или частичное совпадение начиная с начала строки? Если первое — то оно так работать не будет, ну найдёте Вы короткий матч, а как узнать из этого, можно ли сматчить всю строку? Тогда, наверное, придётся таки преобразовывать NFA в DFA и честно по нему идти.

а вот тут по подробнее, есть кейс, когда реализация не работает?

C>Ещё более технический момент: такое задание структуры у меня только чистый Ц понял, и то заорал, что неконстантный массив, пришлось статиком делать. Лучше бы попроще, поуниверсальней.

тык чистый С же это и есть. Но вообще вроде по стандарту всё.

Здравствуйте, Nick-77, Вы писали:

N7>да там и сообщение не меняется... или только у меня прав нет?

Странно, вроде свои всем можно редактировать, иконка карандаша над прямоугольником, сверху-справа.

N7>я ж нуб, учусь типа... хочу регэксп реализовать полноценный. КМП разборщик это что?

О, полноценный регэксп — это круто! КМП — алгоритм Кнута-Морриса-Пратта для нахождения ближайшего вхождения заданной подстроки, чтобы не перестартовывать по одному символу и не проверять всё заново. Он, правда, не умеет с вопросами работать. Там основная идея — помнить, начиная с какого места и сколько символов шаблона уже сматчены, и если очередной символ фэйлит продолжение, то уменьшать длину матча на заранее определённую величину, на неё же и продвигать возможное начало вправо. Для этого он перед началом работы для каждого начального куска шаблона находит максимальный собственный суффикс, являющийся одновременно и префиксом. При этом, переключившись на него, мы уже уверены, что он точно подходит, а до него никто не подходит. С вопросами в шаблоне будет проблемка, мы сможем найти ближайший возможный перескок (тем же способом), но должны будем ещё убедиться, что бывшие под вопросами символы совпали с невопросными. В итоге мы в худшем случае умножим сумму длин шаблона и строки на число вопросов в данном межзвёздном куске шаблона, что может быть таки выгодным. Ещё есть вариант построения детерминированного автомата, но, боюсь, число состояний может оказаться чудовищным, типа 2^длина_шаблона, то есть сработает только для совсем коротких шаблонов. Хотя может я ошибаюсь, и всё более радужно, в любом случае попробовать не повредит. На курсере есть коротенькие курсы алгоритмов по строкам, по ДНК, лекции можно глянуть бесплатно. Ещё был курс по автоматам от Ульмана, но видимо выкинули, теперь он только на Стенфорде. Для общих регэкспов теория автоматов точно не помешает.

N7>а вот тут по подробнее, есть кейс, когда реализация не работает?

Пока не придумал, может и тут катастрофически пессимизирую

N7>тык чистый С же это и есть. Но вообще вроде по стандарту всё.

Странно, а ideone.com ругается. Там вроде гнусь, может -std=c11 не включили? Хотя ещё более хорошим тоном написания программ на Ц считается такой, чтобы они и крестами компилились

Здравствуйте, Nick-77, Вы писали:

Если тебе нужен полноценный regexp, то тебе необходимо вооружится теорией автоматных языков с недетерминированными конечными автоматами (НДК) с экспилон (е) переходами и ты у цели. Рекомендую книгу моего преподавателя Карпова Юрия Глебовича "Теория автоматов". Ну или ищи, что тебе по вкусу.

N7>>да там и сообщение не меняется... или только у меня прав нет?

C>Странно, вроде свои всем можно редактировать, иконка карандаша над прямоугольником, сверху-справа.

у мну нету, видимо рангом не дорос (

N7>>я ж нуб, учусь типа... хочу регэксп реализовать полноценный. КМП разборщик это что?

C>О, полноценный регэксп — это круто! КМП — алгоритм Кнута-Морриса-Пратта для нахождения ближайшего вхождения заданной подстроки, чтобы не перестартовывать по одному символу и не проверять всё заново. Он, правда, не умеет с вопросами работать. Там основная идея — помнить, начиная с какого места и сколько символов шаблона уже сматчены, и если очередной символ фэйлит продолжение, то уменьшать длину матча на заранее определённую величину, на неё же и продвигать возможное начало вправо. Для этого он перед началом работы для каждого начального куска шаблона находит максимальный собственный суффикс, являющийся одновременно и префиксом. При этом, переключившись на него, мы уже уверены, что он точно подходит, а до него никто не подходит. С вопросами в шаблоне будет проблемка, мы сможем найти ближайший возможный перескок (тем же способом), но должны будем ещё убедиться, что бывшие под вопросами символы совпали с невопросными. В итоге мы в худшем случае умножим сумму длин шаблона и строки на число вопросов в данном межзвёздном куске шаблона, что может быть таки выгодным. Ещё есть вариант построения детерминированного автомата, но, боюсь, число состояний может оказаться чудовищным, типа 2^длина_шаблона, то есть сработает только для совсем коротких шаблонов. Хотя может я ошибаюсь, и всё более радужно, в любом случае попробовать не повредит. На курсере есть коротенькие курсы алгоритмов по строкам, по ДНК, лекции можно глянуть бесплатно. Ещё был курс по автоматам от Ульмана, но видимо выкинули, теперь он только на Стенфорде. Для общих регэкспов теория автоматов точно не помешает.

Ааа я вроде у вирта что-то такое читал, но думаю в ? это не прокатит (будет менее эффективно, чем тупой перебор со сдвигом по одному).


N7>>тык чистый С же это и есть. Но вообще вроде по стандарту всё.

C>Странно, а ideone.com ругается. Там вроде гнусь, может -std=c11 не включили? Хотя ещё более хорошим тоном написания программ на Ц считается такой, чтобы они и крестами компилились

CFLAGS= -Wall -Wextra -std=gnu11 -g -O0

гну11 типа. Кресты что это?

Здравствуйте, Nick-77, Вы писали:

N7>у мну нету, видимо рангом не дорос (

Да вроде бы нет тут рангов. Может поломалось что.

N7>Ааа я вроде у вирта что-то такое читал, но думаю в ? это не прокатит (будет менее эффективно, чем тупой перебор со сдвигом по одному).

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

N7>гну11 типа.

Гну — уже не стандарт, а гну-расширение. Хотя может и стандартом Ц11 скомпилится, надо спробовать.

N7>Кресты что это?

Кресты — это C++.

Здравствуйте, Nick-77, Вы писали:
Корректно, если все ссылки на переменную будут действовать (будут видны) не дольше, чем время жизни этой переменной.
Код не читал.

(кстати, в С++ нет переменных в стеке, есть автоматические переменные)