Porównywanie łańcuchów

Witam jestem raczej początkujący jeśli chodzi o programowanie. Mam do napisania funkcję która ustala zgodność wzorca z łańcuchem. Znak ’ ?’ we wzorcu oznacza zgodność z dowolnym innym znakiem. Znak ’’ oznacza zgodność z dowolnym, również pustym, ciągiem znaków w łańcuchu. Znak różny od ’ ?’ i ’’ oznacza zgodność tylko z samym sobą.
Próbowałem napisać to w taki sposób:

Bool match(char* model, char* string)
{
	int model_lenght = strlen(model);
	int string_lenght = strlen(string);

	while(model_lenght>0 && string_lenght>0)
	{
		if((model[model_lenght-1]==string[string_lenght-1])||(model[model_lenght-1]=='?')||(string[string_lenght]=='?'))
		{
			model_lenght--;
			string_lenght--;
		}
		else
			if(model[model_lenght-1]=='*')
			{
				model_lenght--;
				string_lenght=model_lenght;
			}
			else
				if(string[string_lenght-1]=='*')
				{
					string_lenght--;
					model_lenght=string_lenght;
				}
				else
					return 0;
	}

	if(model_lenght==0 && string_lenght==0)
		return 1;
	else
		return 0;
}

Ale niestety nie działa prawidłowo dla '*'. Szczerze nie mam pomysłu jak ten algorytm ma działać w przypadku gwiazdki :(

bool match(char* str, char* pattern)
{
    bool matchAny = false;
    while (true)
    {
        if (*pattern == '*')
        {
            matchAny = true;
            ++pattern;
        }

        char curr = *str++;
        if (!curr)
        {
            return !*pattern;
        }

        if (*pattern == curr)
        {
            matchAny = false;
            ++pattern;
        }
        else if (!matchAny)
        {
            return false;
        }
    } 
}

Zadanie domowe:

1. Dopisz obsluge wielu gwiazdek pod rzad np. a***b***
2. Dopisz obsluge patternu ?

Powinna byc zmiana dwoch linijek.

Przepraszam że tak późno odpisuję, ale dopiero mogłem się tym zająć.
Wpisałem ten kod do kompilatora i mam wrażenie że nadal nie do końca działa, wszysko jest ok tylko gdy ** jest na końcu.
aaaaaa - a* - true
ale już
aaaaaa - *a - false
Dodatkowo nie rozumiem niektórych fragmentów kodu.

Rozwiazanie z backtrackingiem obsluguje takie rodzaj wzorcow. Jak nie rozumiesz kodu to pytaj konkrety. Polecam najpierw zrozumiec poprzedni kod bo jest prostszy.

bool match(char* str, char* pattern)
{
    bool matchAny = false;
    while (true)
    {
        if (*pattern == '*')
        {
            matchAny = true;
            ++pattern;
        }

        if (!*str)
        {
            return !*pattern;
        }

        if (*pattern == *str)
        {
            if (matchAny)
            {
                if (match(str, pattern))
                {
                    return true;
                }
            }
            else
            {
                ++pattern;
            }
        }
        else if (!matchAny)
        {
            return false;
        }
        ++str;
    } 
}

Wiem że to pewnie głupie pytania ale staram się to dokładnie zrozumieć.
I czy while(true) nie można zastąpić czymś "ładniejszym" ?

 bool match(char* str, char* pattern)
{
    bool matchAny = false;
    while (true)
    {

        if (*pattern == '*')
		//*pattern to wskazanie na pierwszy znak łańcucha ?
        {
            matchAny = true;
            ++pattern;
			//przejście do następnego znaku ? jeżeli tak to czym to się różni od pattern++ ?
        }
 
        char curr = *str++;
		//zapamiętujemy pierwszy znak z str i przechodzimy do następnego ?
        if (!curr)
        {
            return !*pattern;
        }
 
        if (*pattern == curr)
        {
            matchAny = false;
            ++pattern;
        }
        else if (!matchAny)
        {
            return false;
        }
    } 
}

Nieskonczona petle da sie zastapic petla z warunkiem ale w tym przypadku moze to byc ciezkie a powstaly kod moze byc dluzszy i mniej czytelny.
Co do reszty pytan to poczytaj o arytmetyce wskaznikow oraz post- i pre-inkrementacji. W tym kodzie kazda preinkrementacje mozesz zastapic postinkrementacja i bedzie dzialac tak samo.
*ptr to pierwszy znak na co obecnie wskazuje zmienna ptr. Alternatywnie mozna to zapisac ptr[0]·
++ptr to przejscie do kolejnego znaku.
*ptr++ to odczyt pierwszego znaku a nastepnie przejscie do kolejnego.

Poczytałem i już rozumiem tę arytmetykę, ale nie do końca rozumiem jeszcze tylko ten kawałek

            if (matchAny)
            {
                if (match(str, pattern))
                {
                    return true;
                }
            }
            else
            {
                ++pattern;
            }

To jest technika zwana backtrackingiem (w przypadku parserów także zwana recursive descent). Powiedzmy, że masz łańcuch ababb oraz wzorzec a*b . Jak próbujesz dopasować ten wzorzec to masz wybór:

1. Dopasuj łańcuch ab do wzorca a*b
2. Dopasuj łańcuch abab do wzorca a*b
3. Dopasuj łańcuch ababb do wzorca a*b

Tylko 3 opcja daje poprawne dopasowanie. Ale gdy przetwarzasz wzorzec i łańcuch po jednym znaku to nie masz pojęcia, którą opcje wybrać (nawet nie wiesz, że opcja 2 i 3 istnieje gdy jestes na drugim znaku). Dlatego pierwszy algorytm działa niepoprawnie dla takiego wzorca i łańcucha bo zachłannie wybiera zawsze pierwszą opcje. Backtracking rozwiązuje ten problem próbując wszystkie możliwe dopasowania.

        if (*pattern == curr)
        {
            if (matchAny)
            {
                //Tutaj mamy wybór: albo kończymy dopasowanie gwiazdki i wybieramy kolejny znak wzorca albo kontynujemy dopasowywanie gwiazdki
                //Nie wiemy co zrobić więc próbujemy co się stanie jeżeli zakończymy matchowanie gwiazdki
                if (match(str, pattern))
                {
                    //Nasza decyzja okazała się poprawna wzorzec jest dopasowany więc kończymy
                    return true;
                }
                // Decyzja okazała się niepoprawna więc kontynuujemy matchowanie gwiazdki
            }
            else
            {
                //Nie było gwiazdki więc nie ma problemu, nie mamy żadnego wyboru z którym trzeba by się zmagać
                ++pattern;
            }
        }

Dzięki wielkie za pomoc, chyba w miarę to zrozumiałem i cieszę się że czegoś się nauczyłem ;)

Testowałem tę funkcję jeszcze raz i wydaje mi się że nie wykrywa ona zgodności '*" z pustym łańcuchem

No to źle testowałeś:

printf("%d", match("", "*"));

daje 1. Chyba, że coś pozmieniałeś.

Dodałem tylko 1 warunek

if ((*pattern == curr) || (*pattern == '?'))

EDIT:

int main()
{
	printf("%d\n",match("","**"));

	return 0;
}

To mi daje 0.

W zadaniu domowym dałem ci obsługe wielu gwiazdek pod rzad :P
Wystarczy zmiana jednej linijki zeby dzialalo poprawnie (jak rozumiesz ten kod to nie bedziesz mial problemu).

Myślałem że to zadanie domowe było do pierwszego kodu którego nie rozumiałem,, a potem już te zadania pominąłem ;p
Ale myślę że rozwiązałem

while (*pattern == '*')

Jak chcesz jeszcze trochę się z tym pobawić to możesz zoptymalizować sytuacje gdy * jest na końcu wzorca (np. a*).
Obecny kod jest malo wydajny dla tego przypadku a latwo to zoptymalizować.

Hmm, pierwsze co mi przyśzło do głowy to:

        while (*pattern == '*')
        {
            matchAny = true;
			if(++pattern==0)
				return true;
        }

        while (*pattern == '*')
        {
            matchAny = true;
			++pattern;
        }

	    if(*pattern==0)
		    return true;

Zastanawiałem się czy nie *(++patern) ale on już jest powiększony po wyjściu z pętli, chyba że źle myślę.

No tak, nie pomyślałem, wcześniej zostawiłem tą robotę pętli.

if(*pattern==0 && matchAny == true)
    return true;

int MatchesPattern(const char *s, const char *pattern)
{
	size_t prefixSize = strcspn(pattern, "*?");
	if (memcmp(s, pattern, prefixSize) != 0)
		return 0;
 
	pattern += prefixSize;
	s += prefixSize;
 
	if (*pattern == '?')
	{
		return *s && MatchesPattern(s + 1, pattern + 1);
	}
	if (*pattern == '*')
	{
		while (*pattern == '*')
			++pattern;
		if (!*pattern)
			return 1;
		while (*s)
		{
			if (MatchesPattern(s, pattern))
				return 1;
			++s;
		}
		return !*pattern;
	}
	return !*s;
}

http://ideone.com/VeBVeJ

Pierwszą rekursję da się dość prosto wyeliminować:

int MatchesPattern(const char *s, const char *pattern)
{
    while (true)
    {
        size_t prefixSize = strcspn(pattern, "*?");
        if (memcmp(s, pattern, prefixSize) != 0)
            return 0;

        pattern += prefixSize;
        s += prefixSize;

        if (*pattern == '?')
        {
            if (!*s)
            {
                return 0;
            }
            ++s;
            ++pattern;
        }
        else
            break;
    }

    if (*pattern == '*')
    {
        while (*pattern == '*')
            ++pattern;
        if (!*pattern)
            return 1;
        while (*s)
        {
            if (MatchesPattern(s, pattern))
                return 1;
            ++s;
        }
        return !*pattern;
    }
    return !*s;
}