|
Meine Frage:
Hallo!
Um einen Suffixbaum in einen Suffixarray umzuwandeln, muss man ja die Tiefen-Suche anwenden. Tiefen-Suche braucht O(|E|+|V|) Zeit. E-Kanten,V-Knoten.
Warum dann finde ich immer im Internet, dass die Laufzeit um einen SB in einen SA umzuwandeln mittels DFS nur O(|V|) beträgt? Übrigens, das hat auch mein Tutor gesagt.
Meine Ideen:
Darf man Kanten also einfach weglassen?
|
|