Ein Algorithmus hat keinerlei Bezug auf das Betriebssystem und ist auch nicht von irgendeiner Bibliothek abhängig. Der Algorithmus ist nichts anderes als ein Verfahren, dass verwendet wird, um ein Problem zu lösen. Als Verfahren ist der Quellcode gemeint, der etwas bestimmtes tut. C C++ C/C++ Algorithmen Sortieralgorithmen Suchalgorithmen Pattern Matching String Matching Algorithmen Sortieralgorithmen Suchalgorithmen Pattern Matching String Matching Kapitel 25: Algorithmen

25.7. Stringmatching            zurück  Ein Kapitel tiefer  zum Inhaltsverzeichnis

Textverarbeitungsprogramme verwenden für die Bearbeitung von Texten Zeichenkettenfolgen in Form von einzelnen Buchstaben, Nummern oder Sonderzeichen.

Wenn Sie einen Texteditor oder Ähnliches entwickeln wollen, werden Sie auch Funktionen wie das Suchen von Strings oder Teilstrings benötigen; oder etwa die Syntaxhervorhebung einer bestimmten Programmiersprache. Eine weitere Möglichkeit ist das Pattern Matching, das Sie vielleicht aus Perl oder Shell von Linux kennen.

Für solche und weitere Anwendungsmöglichkeiten werden String-Matching-Algorithmen genutzt. Sie funktionieren nach folgendem Prinzip: In einer Textzeichenfolge, wie etwa dem Text in diesem Buch, soll mit einem Suchmuster die Häufigkeit der enthaltenen N-Zeichen und M-Zeichen verglichen werden.

Das Ziel des Kapitels ist es nicht, die Algorithmen anhand mathematischer Formeln zu erklären, sondern eher, die Algorithmen so zu erklären, dass ihr Prinzip, nach dem sie funktionieren, verstanden wird. Auf der Suche nach genaueren Beschreibungen werden Sie im Anhang dieses Buches unter Weiterführende Links fündig.

Als Schnittstelle zu diesen Beispielen soll eine Struktur verwendet werden, welche die Daten von der Kommandozeile entnimmt und für eventuelle Auswertungen speichert.

struct datei{
              char name[LEN];  /* Name der Datei  */
              int gefunden;    /* Anzahl gefunden */
             };

typedef struct datei DATEI;

Sie können diese Struktur gern um weitere Informationen wie die Position der Fundstelle erweitern. In den Beispielen wird jeweils ein Array von Strukturen verwendet. In der Praxis können Sie auch verkettete Listen einsetzen.

Der Aufruf der Programme lautet hierbei immer:

programmname suchstring datei1 … bis datei_n  

Bei all den Zusätzen sollten Sie dennoch das Hauptaugenmerk auf die einzelnen Algorithmen richten. Alle Matching-Algorithmen suchen nach einer bestimmten Textfolge. Sofern Sie an ganzen Wörtern interessiert sind, können Sie den Algorithmus entsprechend anpassen. Dabei sollten Sie darauf achten, dass vor und nach dem Suchstring alle Whitespace-Zeichen beachtet werden (Newline, Tabulator und Space).

25.7.1 Brute-Force-Algorithmus
Der einfachste Algorithmus liegt auf der Hand. Es werden alle infrage kommenden Positionen des Musters in einem Text überprüft, bis das Muster mit dem Text übereinstimmt oder das Ende des Texts gekommen ist. Das komplette Muster wird also beim Vergleich des Texts um eine Position nach vorn gezählt. Dies ist ein Brute-Force-Algorithmus (oder auch grober Algorithmus oder naiver Algorithmus). Hier das simple Beispiel:

Abbildung 25.30: Ablauf des Brute-Force-Algorithmus

Abbildung 25.30: Ablauf des Brute-Force-Algorithmus

Jetzt der Quellcode zu diesem einfachen String-Matching-Algorithmus:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LEN 255
#define MAX_DAT 10
#define MAX_LINE 4096
#define LINE "---------------------------------------\n"

struct datei{
              char name[LEN];  /* Name der Datei  */
              int gefunden;    /* Anzahl gefunden */
             };

typedef struct datei DATEI;

/* int i = der Textzählerstand  */
/* int j = der Musterzählerstand */
int BruteForce(char *muster, char *text)
{
   int i=0, j, cnt = 0;
   int m=strlen(muster);  /*Länge Muster*/
   int n=strlen(text);    /*Länge Text*/
   while (i<=n-m)         /*Solange i kleiner als n-m zum Ende*/
      {   /*Solang Muster und Text gleich j++ */
         for(j=0; j<m && muster[j]==text[i+j]; j++);
            if(j==m)
               {
                  /*Ist die Länge von j gleich der vom Muster ?*/
                  printf("Pos. %3d, ",i);
                  cnt++;
               }
            i++; /*Im Text eine Position weiter*/
      }
   return cnt;
}

int main(int argc, char *argv[])
{
   DATEI suche[MAX_DAT];
   char suchstring[LEN];
   char read_line[MAX_LINE];
   FILE *f;
   int i, j , ret, zeile;

   if(argc < 3)
      {
         fprintf(stderr, "Verwendung: %s suchstring datei1"
                    " <datei2>  - <datei%d>\n",argv[0],MAX_DAT);
         exit(0);
      }

   strncpy(suchstring, argv[1], LEN);
   /* Kommandozeilen-Argumente auswerten */
   for(i=2,j=0; j < MAX_DAT && i < argc; i++,j++)
      {
         strncpy(suche[j].name, argv[i], LEN);
         suche[j].gefunden = 0;
      }
   for(i = 0; i < argc-2; i++)
      {
         f = fopen(suche[i].name, "r");
         if(f == NULL)
            {
               perror(NULL);
               continue;
            }
         zeile = 0;
         printf("\nDatei \"%s\": \n",suche[i].name);
         while( fgets(read_line, MAX_LINE, f) != NULL)
            {
               zeile++;
               ret=BruteForce(suchstring, read_line);
               if(ret != 0)
                  {
                     suche[i].gefunden+=ret;
                     printf(" in Zeile %d\n",zeile);
                     ret=0;
                  }
            }
         printf("Suchergebnisse in \"%s\": %d\n",
                             suche[i].name, suche[i].gefunden);
         printf(LINE);
         fclose(f);
      }
   return 0;
}

Um als Beispiel den Suchstring "ex" und als Muster "a example text" zu verwenden: Die innere for-Schleife wird dabei nur dreimal inkrementiert, und zwar bei jedem Vorkommen des Buchstabens 'e'. Zweimal wird davon ein Ergebnis gefunden. Die Laufzeit des Algorithmus ist natürlich abhängig vom Suchmuster, aber im Durchschnitt hat der Brute-Force-Algorithmus immer ein lineares Zeitverhalten.

25.7.2 Der Algorithmus von Knuth/Morris/Pratt (KMP)
Der Nachteil des Brute-Force-Algorithmus' ist der, dass dieser stur Zeichen für Zeichen, Position um Position vergleicht. Die Programmierer Knuth, Morris und Pratt, nach denen dieser Algorithmus auch benannt ist, haben diesen Algorithmus verbessert (verfeinert). Sie hatten die Idee, die Fehlvergleiche (so genanntes Missmatch) in den weiteren Algorithmus mit einzubeziehen.

Als Beispiel sei diese Textfolge gegeben (text):

lu lalalala lule lulalalas   

Der Suchstring (suchmuster) lautet alalas. Der Vorgang beginnt wie beim Brute-Force-Algorithmus:

Abbildung 25.31: Auf der Suche nach dem Suchstring

Abbildung 25.31: Auf der Suche nach dem Suchstring "alalas" - Start

Hier haben Sie zwischen text[i] und suchmuster[j] keine Übereinstimmung. Daher kann suchmuster um eine Position weitergeschoben werden:

Abbildung 25.32: Keine Übereinstimmung - Suchstring eine Postion weiter

Abbildung 25.32: Keine Übereinstimmung - Suchstring eine Postion weiter

Dies wird so lange wiederholt, bis zwei gleiche Zeichen aufeinander treffen:

Abbildung 25.33: Erstes Zeichen stimmt überein

Abbildung 25.33: Erstes Zeichen stimmt überein

Solange text[i] jetzt gleich mit suchmuster[j] ist, werden i und j inkrementiert:

Abbildung 25.34: Nach fünf Zeichen tritt ein Fehlvergleich auf

Abbildung 25.34: Nach fünf Zeichen tritt ein Fehlvergleich auf

An Position text[9] und suchmuster[5] tritt hier eine Ungleichheit auf. Beim Brute-Force-Algorithmus würde jetzt das Muster wieder um eine Position nach vorn gesetzt werden. Und genau hier greift der Algorithmus von Knuth, Morris und Pratt ein.

Die kleinstmögliche Verschiebung, bei der "alalas" sich mit sich selbst deckt, ist um zwei Stellen:

Abbildung 25.35: Kleinstmögliche Verschiebung des Suchstring selbst

Abbildung 25.35: Kleinstmögliche Verschiebung des Suchstring selbst

Im nächsten Schritt werden dabei auch zwei Stellen weitergeschoben, da Sie ja nun wissen, dass sich der Anfang nicht überlappt. Genauer gesagt, Sie wissen es jetzt, weil ich es Ihnen gesagt habe, aber nicht wie dies programmtechnisch geschieht. Hierfür ist eine Vorlaufphase erforderlich. Aber dazu gleich mehr.

Abbildung 25.36: Verschiebung um Zwei anstatt um eine Stelle
Abbildung 25.36: Verschiebung um Zwei anstatt um eine Stelle

In der Theorie hört sich das alles natürlich recht interessant an. Aber es in die Praxis umzusetzen, ist wesentlich komplizierter. Wie realisieren Sie eine kleinstmögliche Verschiebung um den Suchstring (suchmuster) selbst?

Da die Berechnung einer solchen Verschiebung nicht vom Text abhängig ist, in dem die Suche stattfindet, sondern nur vom Suchtext (suchmuster), kann sie schon vor der eigentlichen Suche erstellt werden. Es wird dabei von einer Vorlaufphase (Preprocessing) gesprochen. Hier der Algorithmus, welcher eine Sprungtabelle aus dem Suchstring selbst für den eigentlichen Suchalgorithmus erstellt.

void init_next(char *suchmuster, int m)
{
   int i, j;
   i = 0;
   j = next[0] = -1;
   /* Solange i kleiner als der Suchstring ist */
   while (i < m)
      {
         while (j > -1 && suchmuster[i] != suchmuster[j])
            j = next[j];
         i++;
         j++;
         if (suchmuster[i] == suchmuster[j])
            next[i] = next[j];
         else
            next[i] = j;
      }
}

Um nochmals zum Szenario zu kommen: Sie verwenden gerade einen Brute-Force-Algorithmus und vergleichen einzelne Zeichen. Findet jetzt ein Missmatch (suchmuster!=text) statt, wird in den bisher gefundenen und übereinstimmenden Zeichen von hinten ein String mit maximaler (L) Länge gesucht, der zugleich Anfang eines weiteren Strings ist. Danach wird das Zeichen mit L+1 (=next[j]) und dem i-ten Zeichen im Text verglichen. Zwei Möglichkeiten gibt es dafür:

Mit next[i] = j stellen Sie sicher, dass j-1 die Länge des größten Endstücks, aber auch das Anfangsstück des Suchstrings ist. Ist suchmuster[i] gleich suchmuster[j], wird mit next[++i]=++j der Wert zugewiesen, da das next-Array immer das nächste Zeichen beinhaltet. Ist dies nicht der Fall, wird der Anfangsteil und das längste Endteil mit dem Muster verglichen, bis es zu einem positiven Vergleich zwischen muster[i] und muster[j] kommt.

Nun noch der eigentliche Algorithmus mit dem Suchstring und dem Textbeispiel, welches eben verwendet wurde (alalas).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 4096

void init_next(char *, int);
void kmpSearch(char *, char *);

int next[MAX];

/* i = Position im Text */
/* j = Position im Muster */
void kmpSearch(char *muster, char *text)
{
   int i=0, j=0;
   int m=strlen(muster);  /*Länge Muster*/
   int n=strlen(text);    /*Länge Text*/

   init_next(muster, m);     /* Tabelle für next berechnen*/

   while (i<n)   /*Solange wir nicht am Ende vom Text sind*/
      {
         while (j>=0 && text[i]!=muster[j])j=next[j];
         i++; j++;
         if (j==m)
            {
                printf("Gefunden an Pos. %d\n",i-j);
                j=next[j];
            }
      }
}

void init_next(char *muster, int m)
{
   int i, j;
   i = 0;
   j = next[0] = -1;
   /* Solange i kleiner als der Suchstring ist */
   while (i < m)
      {
         while (j > -1 && muster[i] != muster[j])
            j = next[j];
         i++;
         j++;
         (muster[i] == muster[j])?(next[i]=next[j]):(next[i]=j);
      }
}

int main()
{
   kmpSearch("alalas", "lu lalalala lule lulalalas");
   return 0;
}

Das vollständige Listing des Brute-Force-Algorithmus' umgeschrieben auf das Programmbeispiel:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 255
#define MAX_DAT 10
#define MAX_LINE 4096
#define MAX 255
#define LINE "_______________________________________\n"

struct datei{
              char name[LEN];  /* Name der Datei  */
              int gefunden;    /* Anzahl gefunden */
             };

typedef struct datei DATEI;

int next[MAX];

int kmp_Search(char *, char *);
void init_next(char *, int);

int kmp_Search(char *muster, char *text)
{
   int i=0, j=0, cnt=0;
   int m=strlen(muster);  /*Länge Muster*/
   int n=strlen(text);    /*Länge Text*/

   init_next(muster, m);     /* Tabelle für next berechnen*/

   while (i<n)   /*Solange wir nicht am Ende vom Text sind*/
      {
         while (j>=0 && text[i]!=muster[j])j=next[j];
         i++; j++;
         if (j==m)
            {
                printf("Gefunden an Pos. %d\n",i-j);
                cnt++;
                j=next[j];
            }
      }
   return cnt;
}

void init_next(char *muster, int m)
{
   int i, j;
   i = 0;
   j = next[0] = -1;
   /* Solange i kleiner als der Suchstring ist */
   while (i < m)
      {
         while (j > -1 && muster[i] != muster[j])
            j = next[j];
         i++;
         j++;
        (muster[i]==muster[j])?(next[i]=next[j]):(next[i]=j);
      }
}

int main(int argc, char *argv[])
{
   DATEI suche[MAX_DAT];
   char suchstring[LEN];
   char read_line[MAX_LINE];
   FILE *f;
   int i, j , ret, zeile;

   if(argc < 3)
      {
         fprintf(stderr, "Verwendung: %s suchstring datei1 "
                      "<datei2> ... <datei%d>\n",argv[0],MAX_DAT);
         exit(0);
      }

   strncpy(suchstring, argv[1], LEN);
   /* Kommandozeilen-Argumente auswerten */
   for(i=2,j=0; j < MAX_DAT && i < argc; i++,j++)
      {
         strncpy(suche[j].name, argv[i], LEN);
         suche[j].gefunden = 0;
      }
   for(i = 0; i < argc-2; i++)
      {
         f = fopen(suche[i].name, "r");
         if(f == NULL)
            {
               perror(NULL);
               continue;
            }
         zeile = 0;
         printf("\nDatei \"%s\": \n",suche[i].name);
         while( fgets(read_line, MAX_LINE, f) != NULL)
            {
               zeile++;
               ret=kmp_Search(suchstring, read_line);
               if(ret != 0)
                  {
                     suche[i].gefunden+=ret;
                     printf(" in Zeile %d\n",zeile);
                     ret=0;
                  }
            }
         printf("Suchergebnisse in \"%s\": %d\n",
                              suche[i].name, suche[i].gefunden);
         printf(LINE);
         fclose(f);
      }
   return 0;
}

Der eine oder andere wird mir jetzt entgegnen, dass Kapitel sei viel zu schwer für ein Einsteiger-Buch. Im Prinzip muss ich dem zustimmen. Allerdings möchte ich zum Knuth-Morris-Pratt-Algorithmus sagen, dass hierbei versucht wurde, diesen Algorithmus möglichst einfach zu erklären, ohne viele technische Begriffe aus der Welt der Mathematik und Informatik. Für Hardcore-Programmierer, die mehr Details benötigen, sei auf die weiterführenden Links und die Literatur im Anhang verwiesen.

Außerdem soll nicht unerwähnt bleiben, dass der Knuth-Morris-Pratt-Algorithmus immer noch einer der leichteren String-Matching-Algorithmen ist.

25.7.3 Weitere String-Matching-Algorithmen

Boyer Moore
Der Boyer-Moore-Algorithmus ähnelt dem Brute-Force und ist eine weitere Verbesserung gegenüber dem Knuth-Morris-Pratt-Algorithmus. Auch mit diesem Algorithmus werden Verschiebungen vorgenommen, und nicht mehr infrage kommende Verschiebungen werden übersprungen. Hierfür sind gleich zwei Vorlaufphasen (Preprocessing) notwendig. Genauer gesagt zwei Heuristiken, welche die Schrittweite bei der nächsten Verschiebung vorschlagen:

Karp Rabin
Jeder mögliche String des Musters wird in eine Hash-Tabelle eingetragen. Dafür wird eine spezielle Hash-Funktion geschrieben, welche die Eigenschaft hat, dass sie bei dem Text für Startindex i effizient aus dem vorhergehenden Hashwert (Startindex = i-1) berechnet werden kann. Sind dabei zwei Hashwerte gleich, wird wie beim Brute-Force-Algorithmus vorgegangen. Dies funktioniert nach folgendem Pseudocode:

hash_pattern = hash_wert_des_pattern
hash_text    = hash_wert_der_ersten_m_Zeichen_im_text

do{
      if(hash_pattern == hash_text)
          bruteforce_vergleich
      hash_text = hash_wert_der_nächsten_m_Zeichen_des_Textes
  }while(Text_zu_Ende || bruteforce == wahr);

25.8. Pattern Matching (reguläre Ausdrücke)            zurück  Ein Kapitel höher  zum Inhaltsverzeichnis

Jeder, der mit einer UNIX/Linux-Maschine zu tun hat, kennt wohl die regulären Ausdrücke. Reguläre Ausdrücke sind auch eine Form der Suche nach Zeichenketten, nur erheblich komfortabler und komplexer.

Der Begriff "regulärer Ausdruck" stammt vom Sprachwissenschaftler Noam Chomsky und wird in der Informatik verwendet. Es gibt zwar mehrere Varianten von regulären Ausdrücken, doch haben alle dasselbe Ziel.

Bei einem regulären Ausdruck geht es darum, Muster aus Buchstaben zu beschreiben, und dies zusammen mit Wiederholungen, Alternativen und Abkürzungen für Zeichenklassifizierungen wie Ziffern oder Buchstaben. Das bekannteste Beispiel, womit sogar MS-DOS klar kommt und jeder kennen dürfte, ist die "Wildcard" (*):

dir t*.txt 

oder unter UNIX:

ls -l t*.txt

So werden alle Textdateien ausgegeben, die mit "t" beginnen und mit ".txt" enden:

text.txt
test.txt
total.txt

Reguläre Ausdrücke sind keine Funktionen, sondern es handelt sich um eine echte Sprache mit formaler Grammatik, bei der jeder Ausdruck eine präzise Bedeutung hat.

Hierzu folgen einige Funktionen in der Praxis. Wobei diejenigen, die mit den regulären Ausdrücken überhaupt nicht vertraut sind, einen kleinen Einblick erhalten, und Anwender, die reguläre Ausdrücke schon häufiger verwendet haben, sehen werden, wie reguläre Ausdrücke in C geschrieben werden können.

Es sei darauf hinwiesen, dass es sich dabei nicht um eine umfassende Anleitung zu regulären Ausdrücken handelt, vielmehr wird ein kurzer Überblick gegeben.

Das Programm, welches erstellt werden soll, liest Zeile für Zeile aus einer Datei aus. Es folgt die erste Funktion, die das Pattern Matching einleitet:

int pmatch(char *ausdruck, char *text)
{
#ifdef __unix__
   if(ausdruck[0] == '^')
#elif __WIN32__
   if(ausdruck[0] == '#')
#endif
      return match(ausdruck+1, text);
   else
      {
         for( ; *text != '\0'; *text++)
            if(match(ausdruck, text))
               return 1;
      }
   return 0;
}

Zuerst wird überprüft, ob der zu matchende Ausdruck am Anfang einer Zeile vorkommt. Dies ist gegeben, wenn der Ausdruck mit dem Zeichen '^' beginnt. Beispielsweise geben Sie als Suchstring folgenden Ausdruck an:

^hallo

Somit müssen die ersten fünf Zeichen einer Zeile in text mit der Zeichenfolge "hallo" übereinstimmen. Beispiele:

hallo welt wie gehts   (Gefunden, da am Annfang der Zeile)
  hallo welt wie gehts (Missmatch -> nicht gefunden)

Im Fall des Zeichens '^' muss der zu matchende Ausdruck inkrementiert werden, damit dieses Zeichen nicht mit verglichen wird.

Bei Nichtverwendung des Zeichens '^' wird die Matching-Funktion ganz normal - Zeichen für Zeichen - aufgerufen.

Hinweis
 

Damit sich dieses Beispiel auch unter MS-DOS/Win32 realisieren lässt, verwenden Sie bitte statt dem Zeichen '^' das Zeichen '#'. Daher auch die bedingte Kompilierung in der Funktion.

Jetzt die Matching-Funktion match():

int match(char *ausdruck, char *text)
{
   if(ausdruck[0] == '\0')
      return 1;
   if(ausdruck[1] == '*')
      return wildcard(ausdruck[0], ausdruck+2, text);
   if(ausdruck[0] == '$' && ausdruck[1] == '\0')
      return *text == '\0';
   if(*text != '\0' && (ausdruck[0]== '.'||
                        ausdruck[0] == *text))
      return match(ausdruck+1, text+1);
   return 0;
}

Zuerst wird getestet, ob das Ende des Patterns schon gekommen ist ('\0'). Danach wird überprüft, ob eine Wildcard (*) angegeben ist. Falls ja, wird die entsprechende Funktion aufgerufen, worauf in Kürze eingegangen wird. Das Zeichen '$' bedeutet beim Matching Zeilenende. Als Beispiel folgende Zeile:

match und$ *.txt 

Damit werden alle Ausdrücke gefunden, bei denen die Zeile mit "und" endet. Einige Beispiele:

Ein Text, der mit und endet und            /*Gefunden*/
Der Text endet nicht mit und und.          /*Missmatch*/
qwert asdf qwert asdf qwert  und           /*Gefunden*/
und was jetzt                              /*Missmatch*/

Um zu überprüfen, dass nicht nach dem Zeichen '$' gesucht wird, sondern, dass es auch wirklich das gewünschte "und" am Ende der Zeile ist (in diesem Fall) ist, wird gleich darauf getestet, ob das nächste Zeichen des Ausdrucks das Endzeichen '\0' ist.

Die nächste Überprüfung

if(*text != '\0' &&(ausdruck[0] == '.' ||  ausdruck[0] == *text))  

testet, ob nicht schon das Ende gekommen ist, und das nächste Zeichen ein beliebiges sein darf (.) oder das Zeichen im Ausdruck mit demjenigen im Text übereinstimmt. Der Punkt steht somit für ein beliebiges Zeichen abgesehen vom Zeichenende. Falls diese Bedingung zutrifft, wird die Funktion rekursiv erneut mit den nächsten Zeichen aufgerufen. Der rekursive Aufruf erfolgt so lange, bis eine der Bedingungen in dieser Funktion einen return-Wert (0 == keine Übereinstimmung oder 1 == Übereinstimmung gefunden) zurückliefert.

Jetzt die (primitive) Wildcard-Funktion:

int wildcard(int c, char *ausdruck, char *text)
{
   for( ;*text != '\0' && (*text == c || c == '.'); *text++)
      if(match(ausdruck, text))
         return 1;
   return 0;
}

Zugegeben, dies ist eine schwache Wildcard-Funktion; aber sie funktioniert. Was bedeutet aber dieses Sternchen beim Pattern Matching? Der Stern zeigt an, dass das letzte Zeichen (oder der Inhalt) mindestens ein- oder mehrmals vorkommen kann, aber nicht muss. Zum Abschluss noch das vollständige Listing:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUF 4096

int pmatch(char *, char *);
int match(char *, char *);
int wildcard(int, char *, char *);
int my_grep(char *, FILE *, char *);

int pmatch(char *ausdruck, char *text)
{
   if(ausdruck[0] == '^')
      return match(ausdruck+1, text);
   for( ; *text != '\0'; *text++)
      if(match(ausdruck, text))
         return 1;
   return 0;
}

int match(char *ausdruck, char *text)
{
   if(ausdruck[0] == '\0')
      return 1;
#ifdef __unix__
   if(ausdruck[1] == '*')
#elif __WIN32__
   if(ausdruck[1] == '~')
#endif
      return wildcard(ausdruck[0], ausdruck+2, text);
   if(ausdruck[0] == '$' && ausdruck[1] == '\0')
      return *text == '\0';
   if(*text != '\0' && ( ausdruck[0] == '.' ||
                         ausdruck[0] == *text))
      return match(ausdruck+1, text+1);
   return 0;
}

int wildcard(int c, char *ausdruck, char *text)
{
   for( ;*text != '\0' && (*text == c || c == '.'); *text++)
      if(match(ausdruck, text))
         return 1;
   return 0;
}

int my_grep(char *ausdruck, FILE *f, char *name)
{
   int n, nmatch=0;
   int line=0;
   char buffer[BUF];
   while(fgets(buffer, sizeof(buffer), f) != NULL)
      {
         line++;
         n = strlen(buffer);
         if(n > 0 && buffer[n-1] == '\n')
            buffer[n-1] = '\0';
         if(pmatch(ausdruck, buffer))
            {
               nmatch++;
               if(name != NULL)
                  printf("%d. ",line);
            }
      }
   if(nmatch!=0)
      printf("Zeile in der Datei %s (insg.%d)\n\n",name,nmatch);
   return nmatch;
}

int main(int argc, char **argv)
{
   int i, nmatch=0;
   FILE *f;

   if(argc <= 2)
      {
         fprintf(stderr, "Verwendung des Programms : "
                         "%s pattern quelle\n\n",*argv);
         exit(0);
      }
   else
      {
         for(i = 2; i<argc; i++)
            {
               f = fopen(argv[i], "r");
               if(NULL == f)
                  {
                     fprintf(stderr, "Konnte %s nicht "
                                     "öffnen\n",argv[i]);
                     continue;
                  }
               if(my_grep(argv[1],f, argv[i]) > 0)
                  nmatch++;
               fclose(f);
            }
      }
   printf("%d Dateien mit passenden Pattern %s gefunden\n",
                                                nmatch,argv[1]);
   return 0;
}

Hier noch ein paar Matching-Beispiele zum Programm (der Programmname sei match und der Name der Datei test.txt). Folgende Textdatei soll gematcht werden:

ist
 ist
  ist.

Matching Gefunden in Zeile
match ^ist test.txt 1
match ^ist$ test.txt 1
match ist$ test.txt 1, 2
match ist test.txt 1,2,3
match .ist test.txt 2,3
match ist. test.txt 3
match .s. test.txt 1,2,3
match .s.$ test.txt 1,2
match ^...$ test.txt 1
match i*. test.txt 1,2,3
match ^i*. test.txt 1

Tabelle 25.2: Einige Matching-Beispiele

Sie sehen schon, was für einen gewaltigen Funktionsumfang Sie mit wenigen Zeilen Code auf die Beine stellen können. Dabei stellt das Programm und das bisher vorgestellte Pattern Matching nur einen Bruchteil dessen dar, wozu Pattern Matching wirklich in der Lage ist. Weitere Pattern-Matching-Zeichen und ihre Bedeutungen finden Sie bei den weiterführenden Links und Literaturempfehlungen im Anhang.

Sollten Sie also für Ihr Programm reguläre Ausdrücke benötigen, können Sie eigene Funktionen schreiben oder auf entsprechende Funktionen der Headerdatei <regex.h> zugreifen. Allerdings entsprechen diese Funktionen dem POSIX-Standard und sind vorwiegend in der UNIX-Welt zu Hause. MS-Windows-Anwender können diese Bibliothek aber zum Beispiel mit dem gcc-Compiler unter der Cygwin-Umgebung auch verwenden.

Weiter mit Kapitel 26: Sicheres Programmieren            zum Inhaltsverzeichnis