Wprowadzenie

Artykuł omawia procedurę porównującą łańcuch ze wzorcem w którym użyto znaków wieloznacznych (ang. wildcards) znanych z DOS-a:

• ? (pytajnik) — zastępuje pojedynczy znak
• * (gwiazdka) — zastępuje dowolną liczbę (także zero) znaków

Przedstawione funkcje zostały przesłane na grupę dyskusyjną pl.comp.lang.c.

Algorytm

Gdy wzorzec zawiera tylko pytajniki sprawdzenie jest bardzo łatwe:

int str_quotcmp(const char *sring, const char* pattern)
{
 char* s = (char*)string;
 char* p = (char*)pattern;

 while (*s && *p)
   {
    if ((*p != ?') && (*s != *p)) return 0;
    s++;
    p++;
   }
 return 1;
}

Jeśli jednak we wzorcu są gwiazdki (ang. asterisk) to sprawa nieco się komplikuje. Jak zostało napisane gwiazdka zastępuje dowolny ciąg liter, należy więc sprawdzić czy w łańcuchu istnieje taki fragment tekstu który będzie pasował do wzorca (poczynając od gwiazdki). Co jednak jeśli we wzorcu występuje większa liczba gwiazdek? — należy wziąć fragment wzorca spomiędzy dwóch kolejnych.

Proszę prześledzić przykład:

wzorzec = "as*ler*cor*r"
łańcuch = "assembler corner"

Pierwszym fragmentem wzorca jest as — ponieważ nie ma przed nim gwiazdki musi on dokładnie pasować do początku łańcucha i tak jest.

wzorzec = "*ler*cor*r"
łańcuch = "sembler corner"

Następnym fragmentem wzorca jest ler, przed nim występuje gwiazdka, czyli trzeba sprawdzić jego wszystkie możliwe położenia.

Najpierw porównany zostanie z fragmentem łańcucha sem — oczywiście nie pasuje. Następnie brane są kolejne 3-literowe fragmenty łańcucha: emb, ble, a w końcu ler który rzecz jasna jest identyczny.

wzorzec = "*cor*r"
łańcuch = " corner"

Postępując tak samo jak wcześniej dojdziemy do wniosku, że łańcuch pasuje do wzorca.

Implementacja

Poniższa procedura zwraca 1 gdy łańcuch pasuje do wzorca.

int match_pattern(const char* string, const char* pattern)
{
 char* p = (char*)pattern;
 char* s = (char*)string;

 char  prev_asterisk;
 char* asterisk;

 int  len;
 while (*p)
  {
  if ((prev_asterisk = *p) == '*') p++; // jeśli bieżący znak jest gwiazdką
                                       // przeskocz go (prev_asterisk
                                       // przechowuje o tym informację)
   if (!*p) break;            // w przypadku gdy był to ostatni znak kończ

   asterisk = strchr(p, '*'); // znajdź kolejne wystąpienie gwiazdki

   // wyznacz długość fragmentu wzorca
   if (asterisk) len = (int)asterisk-(int)p;
            else {
                  len = strlen(p);
                  asterisk = &p[len];
                 }

   if (prev_asterisk == '*') // sprawdzamy dowolną przerwę
     {
      char* temp = s;
      while (*temp)
        {
         if (str_quotcmp2(p, temp, len)) break;
         temp++;
        }
     if (!*temp) return 0;   // jeśli doszliśmy do końca 'string'
                             // znaczy to, że fragment wzorca nie występuje
                             // w łańcuchu
     p = asterisk;
     s = temp+len;
     }
   else  // bez przerw, dokładne dopasowanie
     {
      if (!str_quotcmp2(p, s, len)) return 0;
      p = asterisk;
      s+= len;
     }
  }
 return 1;
}

Funkcja str_quotcmp2 jest taka sama jak przedstawiona na początku str_quotcmp, lecz jako warunek stopu została przyjęta długość fragmentu wzorca.

int str_quotcmp2(const char *sring, const char* pattern, int len)
{
 char* s = (char*)string;
 char* p = (char*)pattern;

 while (*s && len)
   {
    if ((*p != '?') && (*s != *p)) return 0;
    s++;
    p++;
    len--;
   }
 return (len == 0);
}