Grundlegendes zum Ukkonen-Algorithmus für Suffixbäume [duplizieren]
Diese Frage hat hier bereits eine Antwort:
Der Suffix-Tree-Algorithmus von Ukkonen in Klartext 6 AntwortenIch arbeite mit Ukkonens Algorithmus zum Erstellen von Suffix-Bäumen, verstehe jedoch einige Teile der Erklärung des Autors für die Komplexität der linearen Zeit nicht.
Ich habe den Algorithmus gelernt und ihn codiert, aber das Papier, das ich als Hauptinformationsquelle verwende (siehe unten), ist an einigen Stellen verwirrend, sodass mir nicht klar ist, warum der Algorithmus linear ist.
Irgendeine Hilfe? Vielen Dank.
Link zu Ukkonens Artikel:http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf