Naive Textsuche

Die naive Suche ist ein Textsuchalgorithmus.

Idee

• Text von rechts nach links durchlaufen
• An jeder Position wird das Muster von links nach rechts zeichenweise mit dem Text verglichen
• Bei Ungleichheit wird zum nächsten Zeichen übergegangen

Komplexität

Im worst case muss jede Position maximal oft ohne Ergebnis durchlaufen werden:

Im average case stimmt häufig bereits das erste Zeichen des Musters nicht überein:

Implementierung

int NaiveSearch(char Text[], int n, char Muster[], int m) {
 
	int count = 0;
	
	for (int i = 0; i <= n - m; i++) {
	
		bool match = true;
		
		for (int j = 0; j < m; j++) {
			if (Text[i+j] != Muster[j])
				match = false; break;
		}
		
		if (match) count++;
	}
	
	return count;
}