Diese Frage hat hier bereits eine Antwort:

Ich 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