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 Auffinden von Runs als auch zur Konstruktion des Suffix Arrays benötigt.

Typ

Masterarbeit.

Bearbeiter

Das sollten Sie mitbringen

  • Spaß an algorithmischen Problemstellungen
  • gute Programmierkenntnisse in C++

Betreuer

Bei Interesse wenden Sie sich bitte an Johannes Fischer oder Florian Kurpicz

 
Last modified: 2019-08-06 13:01 (external edit)
DokuWikiRSS-Feed