sablon

#include <cstdio>
#include <string.h>

const int LEN = 1001;
FILE *fin, *fout;
char temp[LEN], sab[LEN], str[LEN];


// transform a template like "ab**c****" into "ab*c*"
void safety()
{
    char *a = temp, *b, *c = sab;
    while( (b = strstr(a, "**")) ) {    // find first occurence (b) of more than one '*'
        memcpy(c, a, b - a + 1);        // copy everything up to b to c
        c += b - a + 1;
        a = b;
        while(*(++a) == '*');           // discard remaining '*' characters from b (now equal to a)
    }
    strcpy(c, a);                       // copy remaining characters
    strcat(c, " ");                     // ' ' signals the end of a string (it's different from '/0')
}

// does the template sab match the str?
bool isStrMatch()
{
    int i = 0, L;
    strcpy(temp, sab);                  // we'll later modify the contents of m
    char *m = temp, *w = str;           // m = match (or mask), w = word

    // match the start of the string
    while ( (m[i] == w[i] || m[i] == '?') && m[i] && w[i] ) ++i;

    if (!m[i] && !w[i]) return true;    // no '*' in m and strigs match perfectly
    else if (m[i] != '*') return false; // mismatch occured

    // initially we presumed m was in the form of (S0*S1*S2...*Sn)
    // we matched S0 so add i to m to make it in the form of "*S1*S2*S3...*Sn"
    // where S1, S2 are strings of one or more letters and Sn (is)/(ends in) ' '
    m += i, w += i;

    while(*m && *w) {
        m++;                            // m is now S1*S2...*Sn
        char *p = strchr(m, '*');
        if (p) *p = '\0';

        // m is now "S1", m + 1 is "S2...*Sn"
        if ( !(w = strstr(w, m)) ) return false;
        i = strlen(m);
        m += i, w += i;
        if (p) *p = '*';                       // restore p's value, otherwise *m will fail
    };
    if (*w) return false;
    return true;
}

int main()
{
    int nr;
    fin = fopen("sablon.in", "rt");
    fout = fopen("sablon.out", "wt");
    fscanf(fin, "%d", &nr);
    fscanf(fin, "%s", temp);
    safety();
    for (int i = 1; i <= nr; i++) {
        fscanf(fin, "%s", str);
        strcat(str, " ");               // see safety()
        if (isStrMatch()) fprintf(fout, "%d\n", i);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}