In der zweiten Runde des 33. Bundeswettbewerbs Informatik wurde die folgende Aufgabe gestellt:

“[…] Das Genom, die Folge der Basen in den Chromosomen, ist für den Menschen inzwischen vollständig bekannt. Für weitergehende Forschungen bezüglich der Heilung von Krankheiten ist es allerdings notwendig, das Genom genauer zu untersuchen, etwa auf wiederholt vorkommende Basenfolgen, auch Repetitionen genannt. Schreibe ein Programm für eine solche Untersuchung, das eine Zeichenkette sowie zwei Zahlen k und l einliest und diejenigen Teilzeichenketten ausgibt, die (a) lang sind (mindestens l Zeichen), (b) häufig (mindestens k-mal) in der Zeichenkette auftreten und © maximal (nicht Teil einer längeren und gleich häufigen Teilzeichenkette) sind. […]”

Zur Lösung dieser und ähnlicher Aufgaben sind zwingenderweise fortgeschrittene Algorithmen und Datenstrukturen notwendig, da die Programme ansonsten quadratischen Platzbedarf hätten und damit auf realistisch großen Eingaben kein Ergebnisse liefern würden.

Ein Beispiel für fortgeschrittene Datenstrukturen sind Suffixbäume und Suffix-Arrays. Schnelle Algorithmen zur Zeichenkettensuche sind z.B. der Boyer-Moore-Algorithmus. In dieser kleinen Vorlesung wollen wir diese und ähnliche Verfahren kennenlernen und auf großen Texten ausprobieren, so dass u.a. die obige Aufgabe gelöst werden kann.

Dauer: 2x45min, dazwischen Pause 15min.

Der in der Vorlesung entwickelte Code kann heruntergeladen werden. (Einfach in .java umbennen!)