Chasolimp

String-Algorithmen und Pattern Matching in der Informatik-Olympiade

String-Algorithmen und Pattern Matching in der Informatik-Olympiade

Wer sich ernsthaft auf eine Informatik-Olympiade vorbereitet, kommt an String-Algorithmen früher oder später nicht vorbei. Textverarbeitung gehört zu den klassischen Aufgabengebieten — von der einfachen Mustererkennung bis hin zu komplexen mehrdimensionalen Suchproblemen. Dabei gilt: Wer nur den naiven Ansatz kennt, gerät bei langen Eingaben schnell ins Zeitlimit.

Warum String-Algorithmen in der Olympiade zählen

Bei Wettbewerben wie dem Bundeswettbewerb Informatik tauchen Textverarbeitungsaufgaben regelmäßig auf — ob als Hauptproblem oder als Teilkomponente einer größeren Lösung. Das liegt daran, dass Strings eine universelle Datenstruktur sind: DNA-Sequenzen, Quellcode, natürliche Sprache, Protokolldateien — all das lässt sich als Zeichenkette modellieren.

Der Schlüssel liegt nicht im Auswendiglernen von Code, sondern im Verstehen der zugrunde liegenden Ideen. Wer weiß, warum ein Algorithmus funktioniert, kann ihn auch unter Wettkampfdruck korrekt implementieren.

Der naive Ansatz und seine Grenzen

Der einfachste Weg, ein Muster P der Länge m in einem Text T der Länge n zu finden, ist das sogenannte Sliding Window: Man schiebt P Schritt für Schritt über T und vergleicht an jeder Position zeichenweise.

Text:    ABCABCABCABD
Muster:  ABCABD
         ↑ Vergleich starten

Das funktioniert — ist aber im schlechtesten Fall O(n·m). Bei n = 10^6 und m = 10^3 wären das bis zu eine Milliarde Operationen. Für Olympiade-Aufgaben mit strikten Zeitlimits ist das oft nicht akzeptabel.

KMP: Lineare Suche durch Vorwissen

Der Knuth-Morris-Pratt-Algorithmus löst dieses Problem elegant: Statt nach einem Fehlvergleich wieder von vorn zu beginnen, nutzt er die bereits verarbeiteten Informationen aus. Das Herzstück ist die Präfixfunktion (auch Failure Function genannt).

Die Präfixfunktion aufbauen

Für ein Muster P berechnet man für jede Position i die Länge des längsten echten Präfixes von P[0..i], das gleichzeitig Suffix ist.

Beispiel für P = "ABCABD":

Index Zeichen π-Wert
0 A 0
1 B 0
2 C 0
3 A 1
4 B 2
5 D 0

Diese Tabelle wird in O(m) Zeit berechnet. Der anschließende Suchlauf über den Text benötigt O(n). Insgesamt ergibt sich eine Laufzeit von O(n + m) — ein enormer Gewinn gegenüber dem naiven Verfahren.

Implementierung in Python

def kmp_failure(pattern):
    m = len(pattern)
    pi = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[k] != pattern[i]:
            k = pi[k - 1]
        if pattern[k] == pattern[i]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    pi = kmp_failure(pattern)
    matches = []
    k = 0
    for i in range(n):
        while k > 0 and pattern[k] != text[i]:
            k = pi[k - 1]
        if pattern[k] == text[i]:
            k += 1
        if k == m:
            matches.append(i - m + 1)
            k = pi[k - 1]
    return matches

Rabin-Karp: Hashing als Werkzeug

Ein anderer klassischer Ansatz ist der Rabin-Karp-Algorithmus. Er berechnet einen Hashwert für das Muster und verschiebt dann ein gleichlanges Fenster durch den Text — mit einem sogenannten Rolling Hash, der in O(1) aktualisiert wird.

Der große Vorteil: Rabin-Karp lässt sich leicht auf die Suche nach mehreren Mustern gleichzeitig oder auf 2D-Pattern-Matching ausdehnen — beides kommt in Olympiade-Aufgaben vor. Die durchschnittliche Laufzeit beträgt O(n + m), im schlechtesten Fall (bei Hashkollisionen) O(n·m), was in der Praxis aber selten auftritt.

def rabin_karp(text, pattern, base=31, mod=10**9+7):
    n, m = len(text), len(pattern)
    ph = sum(ord(pattern[i]) * pow(base, i, mod) for i in range(m)) % mod
    th = sum(ord(text[i]) * pow(base, i, mod) for i in range(m)) % mod
    power = pow(base, m, mod)
    matches = []
    if th == ph and text[:m] == pattern:
        matches.append(0)
    for i in range(1, n - m + 1):
        th = (th - ord(text[i - 1])) * pow(base, mod - 2, mod) % mod * power % mod
        th = (th + ord(text[i + m - 1]) * pow(base, m - 1, mod)) % mod
        if th == ph and text[i:i+m] == pattern:
            matches.append(i)
    return matches

Z-Funktion: Vielseitig und unterschätzt

Weniger bekannt, aber mindestens ebenso nützlich ist die Z-Funktion. Für einen String s der Länge n gibt Z[i] an, wie lang das längste Präfix von s ist, das mit dem Teilstring s[i..] übereinstimmt.

Das klingt abstrakt, löst aber Pattern-Matching in O(n + m) durch einen einfachen Trick: Man konkateniert P + "$" + T (wobei $ ein Trennzeichen ist, das in keinem der Strings vorkommt) und berechnet die Z-Funktion des Gesamtstrings. Alle Positionen, an denen Z[i] == m gilt, sind Fundstellen des Musters.

Die Z-Funktion ist in Olympiade-Aufgaben oft die schnellste Lösung zu implementieren, weil sie konzeptionell einfacher ist als KMP.

Boyer-Moore und der Blick von rechts

Der Boyer-Moore-Algorithmus verfolgt eine andere Philosophie: Er vergleicht von rechts nach links und kann bei einem Fehlvergleich mehrere Zeichen überspringen. In der Praxis — besonders bei langen Alphabeten — ist er oft schneller als KMP, auch wenn die Worst-Case-Komplexität höher ist.

Für Olympiade-Aufgaben ist Boyer-Moore weniger verbreitet, weil seine Implementierung fehleranfälliger ist. Trotzdem lohnt es sich, das Bad Character-Prinzip zu verstehen, da es eine wichtige algorithmische Idee transportiert.

Typische Olympiade-Aufgabentypen

Wer sich auf Informatik-Olympiaden vorbereitet, sollte folgende Aufgabenklassen kennen:

  • Musterhäufigkeit: Wie oft kommt P in T vor?
  • Längste gemeinsame Teilzeichenkette: Zwei oder mehr Strings, größte Übereinstimmung gesucht.
  • Periodizität: Ist T eine Wiederholung eines kürzeren Musters? (KMP-Failure-Function!)
  • Anagrammsuche: Alle Fenster der Länge m in T, die eine Permutation von P darstellen.
  • Palindrome: Manacher-Algorithmus für alle Palindrome in O(n).
  • Suffixarrays: Für fortgeschrittene Aufgaben mit langen Strings und mehreren Anfragen.

Tipps für die Wettkampfvorbereitung

Die Lektüre von Lehrmaterialien reicht nicht aus — das Entscheidende ist das eigene Implementieren. Gute Ressourcen sind der Kurs zu Stringalgorithmen der FU Berlin sowie die Skripte der Universität Tübingen zum Pattern Matching.

Konkrete Übungsschritte:

  1. KMP von Grund auf implementieren — ohne Vorlage. Den Fehlerkorrekturschritt (den while-Loop) wirklich verstehen.
  2. Testfälle selbst konstruieren — insbesondere Randlfälle: leeres Muster, Muster größer als Text, vollständige Übereinstimmung.
  3. Laufzeitmessungen vergleichen — naiven Ansatz und KMP auf langen Inputs gegenüberstellen.
  4. Z-Funktion als Alternative implementieren und beide Lösungen für dieselben Aufgaben einsetzen.
  5. Codeforces oder CSES — Plattformen mit dedizierten String-Aufgaben, vom einfachen Substring-Matching bis zum Suffixarray.

Wer alle drei Kernalgorithmen — KMP, Z-Funktion und Rabin-Karp — sicher beherrscht und weiß, wann welcher einzusetzen ist, hat für die große Mehrheit aller String-Olympiadeaufgaben das nötige Handwerkszeug beisammen.

Quellen und weiterführende Links: