Laufzeitanalyse

Eine naive Implementierung von Ukkonens Algorithmus braucht in Phase i+1 für Erweiterung j Zeit O(i+1-j), d.h. für alle Erweiterungen Zeit O(i²) und somit für die m Phasen Zeit O(m³). Wir werden nun eine Reihe von Verbesserungen zum trivialen Ansatz einführen und zeigen, daß diese Verbesserungen in der Summe die Laufzeit auf O(m) drücken. Die erste solche Verbesserung besteht im Einfügen gewisser Zeiger in den impliziten Suffix-Baum.