Back to all cards Back to course

Naive Textsuche

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Naive Suche prüft für jede Textposition, ob das Muster passt. Bei Mismatch verschiebt sie um 1.

Einfach zu verstehen, aber langsam auf langen Texten mit wiederkehrenden Mustern.

Erste Fundstelle: Find the Index of the First Occurrence in a String [1].

$$T[s:s+m]\stackrel{?}{=}P$$

Wo gebraucht

Kleine Pattern, einmalige Suchen, Lehrbasis. In Hot Paths durch indexOf, Automaten oder Indexstrukturen ersetzen.

Vertiefung

Die naive Textsuche richtet das Muster nacheinander an jeder möglichen Startposition des Textes aus. Für eine Ausrichtung werden Zeichen von links nach rechts verglichen, bis ein Unterschied gefunden oder das gesamte Muster bestätigt wird.

Nach einem Unterschied verschiebt das Verfahren das Muster um eine Position und beginnt den Vergleich erneut. Bereits erkannte Übereinstimmungen werden dabei nicht systematisch genutzt. Die Methode ist dennoch wertvoll, weil sie kurz, korrekt und bei kleinen Eingaben oder kurzen Mustern oft ausreichend ist.

Schwierigkeitsstufen

Alle Ausrichtungen eines Musters in einem kurzen Text prüfen.
Frühe Abbrüche bei ungleichen ersten Zeichen nachvollziehen.
Eingaben konstruieren, die viele wiederholte Vergleiche verursachen.

Fallstricke

Die letzte zulässige Startposition wird leicht durch eine falsche Schleifengrenze ausgelassen. Auch leere Muster brauchen eine ausdrücklich gewählte Semantik, damit Implementierung und Tests übereinstimmen.

Sources

[1]https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/Return to text

University approvals: 0

Tasks

Question 1

Wie weit schiebt die naive Suche nach einem Mismatch typischerweise?

um die Musterlänge

um 1

um n

gar nicht

Question 2

Warum beginnt die naive Suche nach einem späten Fehlvergleich an der nächsten Textposition neu?

Sie besitzt keine vorberechnete Information über nutzbare Musterstruktur.

Der Text darf nur einmal gelesen werden.

Jeder Fehlvergleich beweist, dass das Muster nirgends vorkommt.

Die Musterlänge wird nach jedem Vergleich kleiner.

Question 3

Implementiere eine naive Textsuche. Gib den ersten Startindex des Musters oder -1 zurück.

Hint

String.length() liefert die Länge, charAt(i) ein Zeichen. Zeichen werden mit == oder != verglichen.

class NaiveSearch {
  static int indexOfNaive(String text, String pat) {
    // TODO
    return -1;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy