Regex grob und Kosten

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Regex sind mächtig, aber können backtracken und teuer werden. Für festes exaktes Muster sind KMP oder indexOf oft klarer und vorhersehbarer.

naive vs KMP-Komplexität gegenüberstellen.

Wo gebraucht

Validierung, Log-Extraktion, Routing-Regeln. Katastrophale Backtracking-Regex ist ein bekannter DoS-Vektor; einfache Pattern oder possessive Quantifier bevorzugen.

Vertiefung

Reguläre Ausdrücke beschreiben Mengen von Zeichenfolgen durch Verkettung, Alternativen und Wiederholungen. Viele praktische Engines ergänzen Rückreferenzen und weitere Konstrukte. Dadurch ist ihr Verhalten mächtiger als das klassischer endlicher Automaten und ihre Laufzeit schwieriger vorherzusagen.

Mehrdeutige, verschachtelte Wiederholungen können sehr viele alternative Zerlegungen derselben Eingabe erzeugen. Begrenzte Quantifizierer, eindeutige Teilmuster oder possessive Varianten reduzieren solche Suchräume. Für häufig verwendete Muster lohnt es sich ausserdem, das Pattern einmal zu kompilieren.

Schwierigkeitsstufen

Zeichenklassen, Gruppen und Quantifizierer lesen.
Mehrdeutige Wiederholungen in einem Muster erkennen.
Ein riskantes Muster semantisch gleichwertig und eindeutiger formulieren.

Fallstricke

Ein kurzer Ausdruck ist nicht automatisch billig. Ausserdem bedeutet matches in Java eine Prüfung der gesamten Eingabe, während find nach einem passenden Teilstück sucht.

University approvals: 0

Tasks

Question 1

Wann ist Regex riskant?

Immer bei kurzen Literalen

Bei Mustern mit starkem Backtracking

Nur bei HashSet

Nur bei Bäumen

Question 2

Welche Änderung reduziert bei gleicher Bedeutung häufig riskante Mehrdeutigkeit?

Weitere verschachtelte optionale Wiederholungen ergänzen.

Unklare Wiederholungen durch eindeutigere oder begrenzte Teilmuster ersetzen.

Jede Gruppe mehrfach ineinander kopieren.

Alle Literale durch einen Punkt ersetzen.

Question 3

Implementiere matchesDigits. Der String muss aus mindestens einer Dezimalziffer bestehen.

Hint

String.matches(regex) prüft den gesamten String. In einem Java-Stringliteral muss ein Regex-Backslash als \ geschrieben sein.

class DigitRegex {
  static boolean matchesDigits(String s) {
    // TODO
    return false;
  }
}

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: Intermediate
Completed: 0 users

Creator

Best

BestBuddy