1

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 ?

Community
  • 1
  • 1
w00d
  • 5,416
  • 12
  • 53
  • 85

1 Answers1

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

w00d
  • 5,416
  • 12
  • 53
  • 85