Implementierung: naive Suche

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Implementiere die naive Suche und gib den ersten Index oder -1 zurück.

Wo gebraucht

Referenzimplementierung zum Messen gegen JDK und gegen KMP. Nützlich, um Optimierungen zu begründen statt zu raten.

Vertiefung

Eine direkte Implementierung verwendet eine äussere Schleife über Startpositionen und eine innere Schleife über Musterzeichen. Die Invariante der inneren Schleife lautet: Vor Vergleich j stimmen die ersten j Musterzeichen mit dem Textausschnitt überein.

Ist j gleich der Musterlänge, wurde ein vollständiger Treffer gefunden. Der leere Suchstring kann konsistent an Position null gelten. Ist das Muster länger als der Text, existiert keine zulässige Ausrichtung und die äussere Schleife wird nicht betreten.

Schwierigkeitsstufen

Schleifengrenzen für Text- und Musterlänge setzen.
Die innere Schleifeninvariante zur Korrektheit verwenden.
Alle Treffer einschliesslich Überlappungen sammeln.

Fallstricke

Der Ausdruck text[i + j] benötigt die durch die äussere Grenze garantierte Sicherheit. Ein Abbruch beim ersten ungleichen Zeichen darf nicht versehentlich die gesamte Suche statt nur die aktuelle Ausrichtung beenden.

University approvals: 0

Tasks

Question 1

Implementiere indexOfNaive(text, pattern).

Hint

Nutze length() und charAt(index) für String. Verschachtelte for-Schleifen dürfen getrennte Indexvariablen besitzen.

public class NaiveSearch {
  public static int indexOfNaive(String text, String pattern) {
    // 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.

Question 2

Welche Bedingung zeigt in der inneren Schleife einen vollständigen Treffer an?

Der Startindex ist gleich der Textlänge.

Der Musterindex hat die Musterlänge erreicht.

Das erste Musterzeichen stimmt überein.

Die äussere Schleife hat genau einmal iteriert.

Card Info

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

Creator

Best

BestBuddy