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

int prawda = 0;
int ileGwiazdek(char *); int ilePytajnikow(char *);

bool match(char* wzorzec, char* lancuch) {
    int wzorzec_length=strlen(wzorzec);
    int lancuch_length=strlen(lancuch);
    int j=0; //pozycja lancucha

    for(int i=0; i<wzorzec_length; i++) {
        if((j>=lancuch_length && ileGwiazdek(wzorzec)==0) || ilePytajnikow(wzorzec)>strlen(lancuch))
            return false;
        else if(ileGwiazdek(wzorzec)>0 && j>=lancuch_length)
            return true;

        if(wzorzec[i]=='*') {
            char tempwzorzec[100] = "";
            for(int a=0; a<wzorzec_length; a++) {
                tempwzorzec[a] = wzorzec[i+1];
                i++;
            }

            for(int k=j; k<lancuch_length; k++) { //sprawdzenie poprawnosci dla kazdego mozliwego ciagu lancucha
                int n=lancuch_length-k;
                char templancuch[100]="";

                for(int a=0; a<n; a++) {
                    templancuch[a]=lancuch[k+a];
                }
                if((match(tempwzorzec, templancuch) && ((ileGwiazdek(tempwzorzec)==0 && strlen(templancuch)==strlen(tempwzorzec)) ||
                    ileGwiazdek(tempwzorzec)>0)) || strlen(tempwzorzec)==0)
                    return true;
            }
            return false;
        }
        if(wzorzec[i]=='?' || wzorzec[i]==lancuch[j]) {
            j++;
            continue;
        } else
            return false;
    }

    if(wzorzec_length!=lancuch_length)
        return false;
    return true;
}

int ileGwiazdek(char* slowo) {
    int slowo_length=strlen(slowo);
    int wynik=0;
    for(int j=0;j<slowo_length;j++)
        if(slowo[j]=='*')
            wynik++;
    return wynik;
}

int ilePytajnikow(char* slowo) {
    int slowo_length=strlen(slowo);
    int wynik=0;
    for(int j=0;j<slowo_length;j++)
        if(slowo[j]=='?')
            wynik++;
    return wynik;
}

int main() {
    char wzor[100]; char lanc[100];

    char *wzorkey; char *lanckey;
    int wzorlen, lanclen;

    printf("Podaj wrzozec i lancuch: ");
    scanf("%s", wzor);
    scanf("%s", lanc);

    wzorlen = strlen(wzor) + 1;
    lanclen = strlen(lanc) + 1;

    wzorkey = (char*)malloc(wzorlen * sizeof(char));
    lanckey = (char*)malloc(lanclen * sizeof(char));
    strcpy(wzorkey, wzor);
    strcpy(lanckey, lanc);

    if(match(wzorkey,lanckey))
        printf("TRUE\n");
    else
        printf("FALSE\n");

    free(wzorkey);
    free(lanckey);
    return 0;
}