=====  Efficient Computation of Nearest Smaller Suffixes =====

==== Beschreibung ====
In dieser Arbeit soll eine effiziente Datenstruktur für //next// und //previous smaller suffix//-Anfragen gefunden werden.
Diese Anfragen sollen gegeben einem Text //T[1..n]// und einer Position //i// die Position //j// zurückgeben an der das //vorherige// (//j<i//) bzw. //nächste// (//j>i//) Suffix beginnt, welches lexikographisch kleiner ist (//T[i..n]>T[j..n])//.
Solche Anfragen werden unter anderem zum [[https://epubs.siam.org/doi/pdf/10.1137/15M1011032|Auffinden von Runs]] als auch zur [[https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/baier/gsaca.pdf|Konstruktion des Suffix Arrays]] benötigt.

==== Typ ====
Masterarbeit.

==== Bearbeiter ====
[[staff:ellert|Jonas Ellert]]

==== Das sollten Sie mitbringen ====
  * Spaß an algorithmischen Problemstellungen
  * gute Programmierkenntnisse in C++

==== Betreuer ====
Bei Interesse wenden Sie sich bitte an [[staff:fischer|Johannes Fischer]] oder [[staff:kurpicz|Florian Kurpicz]]