Ukkonen's suffix tree algorithm with Leaf-label

Question

I have read the post Ukkonen's suffix tree algorithm in plain English?. But it is unclear how to get the leaf label using this algorithm.

In suffix tree the leaf-label is the number i such that S[i..n] is the suffix that the leaf represent. If I want such a label will it still be O(n) for the total complexity ?

And how to do it ?

Answer 1

I found a solution. Record another L variable in each node to store the sum of end - start of all ancestors. This value indicates the length of the substring ended at a particular node i.e. for leaf it is the length of the suffix. L is updated whenever a tree node is added or a tree node is split.

Then the leaf-label is just n - leaf.L