Ein Volltextindex speichert eine Menge von Texten meist so, dass alle Muster gefunden werden, die an beliebigen Stellen im Text beginnen. Dies ist in vielen Situationen jedoch nicht gewünscht: manchmal möchte man nur die Muster finden, die an bestimmten (a priori bekannten) Positionen beginnen. Für ein solches Szenario sind jedoch noch keine effizienten Konstruktions-Algorithmen bekannt.

Ziel dieser Abschlussarbeit ist es, ein Platz-effizientes Verfahren für die Konstruktion solcher Textsuchsysteme zu entwickeln. Je nach Fähigkeiten und Interesse der/des Kandidat(i/e)n sind aber auch neue theoretische Erkenntnisse ein mögliches Ziel.

Mindestens 2 der folgenden 4 Voraussetzungen sollten erfüllt sein.

• gute Kenntnisse in C++
• Interesse am Algorithm Engineering
• Spaß an kombinatorischen Problemen und algorithmischen Fragestellungen
• Besuch der VL Text-Indexierung