Der einfachste Algorithmus liegt auf der Hand. Man überprüfe alle in Frage kommende Positionen des Musters in einem Text, bis das Muster mit dem Text übereinstimmt oder wir am Ende vom Text angekommen sind. Das komplette Muster wird also beim Vergleich des Textes um eine Position nach vorne gezählt.

Man spricht dabei vom Brute Force Algorithmus (oder auch grober Algorithmus oder naiver Algorithmus). Hier das simple Beispiel........

a

e

x

a

m

p

l

e

t

e

x

t

1.

e

x

2.

e

x

3.

e

x

4.

e

x

5.

e

x

6.

e

x

7.

e

x

8.

e

x

9.

e

x

10.

e

x

11.

e

x

12.

e

x

13.

e

x

Jetzt wollen wir uns den Quellcode zu diesem einfachen String-Matching-Algorithmus ansehen......

/*Download:brute.c*/ #include <stdio.h> #include <stdlib.h> #include <string.h> /* int i = der Textzählerstand */ /* int j = der Musterzählerstand */ void BruteForce(char *muster, char *text) { int i=0, j; int m=strlen(muster); /*Länge Muster*/ int n=strlen(text); /*Länge Text*/ while (i<=n-m) /*Solange i kleiner wie 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 der Länge von j gleich der vom Muster ?*/ printf("Gefunden an Pos. %d\n",i); i++; /*Im Text eine Position weiter*/ } } int main() { BruteForce("ex", "a example text"); return 0; }

Die Innere for-Schleife wir in unserem Beispiel nur 3 mal Inkrementiert. Und zwar bei allen 'e'-Buchstaben. 2 mal wird davon ein Ergebnis gefunden. Die Laufzeit des Algorithmus hängt natürlich auch wieder abhängig vom Suchmuster. Aber im Durchschnitt hat der Brute Force Algorithmus immer ein lineares Zeitverhalten.

Weiterführende Links:

Brute Force Algorithmus : 

http://www-igm.univ-mlv.fr/~lecroq/string/node3.html#SECTION0030

Naiver Algorithmus : 

http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/naive.htm

Nicht ganz so naiver Algorithmus : 

http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/naive2.htm