[c] porownywanie ciągów znaków

[Sniegu]

Witam.
Za zadanie mam porównać wzorzec z łańcuchem. W wzorcu znak '?' znaczy dowolny znak a '*' dowolny ciąg znaków i zwrócić true lub false. Np:
ab??ca = abzzca
ta*ab=tazzzzzab

Problem pojawia się gdy jest do porównania:
ab*ab = abaaab.
Program po prostu bierze od razu kolejne 'a' i porownuje zamiast przeskoczyc do 'ab'.

Ukryta treść:    

Kod: Zaznacz cały

#include<stdio.h>

#define MAX 100

int strMatch (char *module, char *chain)
{
int true=1;
int false=0;
int condition = true;
int Pos_chain = 0;

for(int Pos_mod = 0; Pos_mod < strlen(module); Pos_mod++)
{
switch (module[Pos_mod])
{
case '?': //jak dowolny to przeskakujemy jeden znak
Pos_chain++;
break;

case '*': //jak x dowolnych, to szukamy pierwszego znaku takiego jak następny po *
while ((Pos_chain < strlen(chain)) && (chain[Pos_chain] != module[Pos_mod + 1]))
Pos_chain++;
break;

default: //jak taki sam, to sprawdzamy czy taki sam
if (module[Pos_mod] != chain[Pos_chain])
{ //i jak nie to kończymy pętlę i false
condition = false;
}
else //a jak tak to go przeskakujemy
Pos_chain++;
break;
}

};
if (Pos_chain != strlen(chain))
condition = false;

return condition;
}

int main()
{
char module[MAX], chain[MAX];
printf ("WRITE MODULE ");
scanf ("%s",module);
printf ("WRITE CHAIN: ");
scanf ("%s",chain);
if (strMatch(module,chain))
printf ("TRUE ");
else
printf ("FALSE ");

return 0;
}

Problem jest w tej części kodu. Dokładnie rozumiem błąd jednak nie mam bladego pojęcia jak go naprawić.

Kod: Zaznacz cały

case '*': //jak x dowolnych, to szukamy pierwszego znaku takiego jak następny po *
while ((Pos_chain < strlen(chain)) && (chain[Pos_chain] != module[Pos_mod + 1]))
Pos_chain++;
break;

Pozdrawiam.

[jarzabek89]

Problem dość ciekawy, rozwiązanie kłopotliwe.
Po pierwsze:
Dodawajmy do dowolnego ciągu literki tak długo, aż następna literka nie będzie odpowiadała literce z łańcucha. Chyba dość oczywiste. Cofnijmy się oczywiście później o jedną literkę.
To rozwiąże problem Twego typu, ale nie rozwiąże kolejnego problemu:
Porównajmy:
ab*ab = abaaabxab
Ten algorytm jako dowolny ciąg znaków potraktuje tylko aa, a powinien aabx.
Z tego nasuwają się różne pomysły. Może analizować tekst z dwóch stron?

[norwimaj]

Nie wiem, jaka złożoność Cię satysfakcjonuje, ale może Ci się to przyda:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Determinizacja_automatu_sko%C5%84czonego

. Może Twój przypadek jest trochę lepszy, niż dla dowolnego automatu.-- 17 lis 2015, o 19:01 --Dokładnie chodzi o to, że zamiast Pos_chain – pojednynczej pozycji w stringu, powinieneś przechowywać listę możliwych pozycji.

[Afish]

Bardzo prosta i dość elegancka implementacja wyrażeń regularnych jest tutaj:
U Ciebie trzeba zamienić kropkę na pytajnik.