Wenn wir einen Text suchen, so ist der einfachste Weg Buchstabe für Buchstabe zu vergleichen. Bei einem normalen Text funktioniert das bereits sehr gut, denn Wörter in menschlicher Sprache unterscheiden sich häufig sehr und es gibt ein relativ großes Alphabet.

Sucht man in einem String „Hallo Welt“ das Wort „Welt“, so geht die Suche bereits sehr schnell: der komplette Text vor dem Fundstück enthält kein 'W', also kann man alle Buchstaben ganz einfach überspringen.

Dieser naive Ansatz lässt sich sehr leicht formulieren:

char const * pattern = "Welt";
char const * text    = "Hallo Welt";
 
int position = 0;
int patternPos;
int temp;
int found = -1;
 
while( text[ position ] )
{
  if( text[ position ] == pattern[ 0 ] )
  {
    int temp = position;
 
    /* Das erste Zeichen passt, also bei Index 1 anfangen */
 
    patternPos = 1;
    ++position;
 
    /* Pattern vergleichen */
 
    while( text[position] && text[ position ] == pattern[ patternPos ] )
      ++position, ++patternPos;
 
    if( !pattern[ patternPos ] ) 
    { 
      /* Pattern vollständig gefunden -> Erfolg! */
      result = temp;
      break;
    }
 
    if( !text[ position ] )
    {
      /* Text zuende -> nix gefunden */
      break;
    }
 
    /* Suchmuster passt nicht */
    position = temp;
  }
 
  ++position;
}

Solange der Text nicht zu Ende ist, und kein 'W' gefunden wird, wird Buchstabe für Buchstabe übersprungen. Sobald das 'W' gefunden wird, wird 'e', 'l' und 't' verglichen, anschließend ist der Text zu Ende und die Schleife bricht ab. Das Suchmuster ist ebenfalls zu Ende, also wurde das komplette Suchmuster gefunden und es gibt ein Resultat.

Ist nur der Text zu Ende, wird die Suche abgebrochen. Wird das Suchmuster nicht gefunden, wird zurück zum 'W' gesprungen, anschließend die Position um eins erhöht und die Suche geht weiter.

Dies funktioniert, wie bereits gesagt, in großen Alphabeten recht gut, da man schnell einen Mismatch feststellt. Was passiert nun, wenn ein Alphabet nur zu kleinen Teilen benutzt wird?

Im All aalen alle Aale herum.

Suchen wir nun das Wort 'alle' in diesem String:

Wie zu sehen ist, sind 22 Vergleiche erforderlich, um bei diesem Algorithmus das Suchmuster im Text zu identifizieren. Wird das Alphabet kleiner, zum Beispiel Binär ('001001001000'), so sind Wiederholungen deutlich wahrscheinlicher, entsprechend häufiger werden Vergleiche, die ins Leere laufen.

Bei normalen Texten, wie Literatur, Diplomarbeiten oder ähnliches, wird diese Problematik seltener auftreten. Nun hat es sich aber zum Beispiel bei GTK eingebürgert, GTK-Funktionen auch mit gtk_ beginnen zu lassen. Jede Suche nach einer GTK-Funktion im Quelltext, wird also ersteinmal gtk_ parsen, um sich dann vielleicht noch in gtk_get_ zu verlaufen um dann - nach 8 erfolgreichen Schritten den ersten Buchstaben zu finden, der nicht passt.

An dieser Stelle setzen nun Optimierungen an.