5

I'm seeking clarification of jogojapan's answer to this question: Ukkonen's suffix tree algorithm in plain English?

Can someone please clarify the following: during step 6 last time the active_point was touched it was set it to (root, 'x', 0) (however edge starting with 'x' did not exist at that moment). The next time the active point is referred to is in the step 7, as if it's already == (root, **'a'**, 0) since it was determined (using active_point?) that suffix 'a' is already in the tree and it's only necessary to increment active_length, so the active_point at the end of the step 7 becomes (root, 'a', 1).

How has active_point been changed from (root, 'x', 0) in the step 6 to (root, 'a', 0) in the step 7?

Community
  • 1
  • 1
some
  • 333
  • 2
  • 7
  • 4
    Stack Overflow has a Q&A format, not a discussion thread format. I think posting a new question was the right approach (as opposed to trying to use answers as comments, as too many new users do only to find those "answers" quickly deleted. However, questions are addressed to the community, not individuals. I can post a comment for you letting jogojapan know about this question, but anyone can answer it. – Adi Inbar Apr 26 '14 at 01:05
  • 1
    Sorry for coming too late. Here is my answer anyway: The last action in step 6 is to insert 'x' at the root. After that is done, the `active_point` needs to be reset to `(root,'\x0',0)` (I should have said so explicitly at the end of step 6, sorry for the omission). Basically, whenever we insert a suffix, we need to update the `active_point`. So with `(root,'\x0',0)` we enter step 7, and in step 7 we insert `a`, but because it's already there, we update `active_point` to `(root,'a',1)` -- that's the same thing as in step 4, and whenever we insert something and find it's already there. – jogojapan Apr 26 '14 at 04:44
  • Thanks! BTW, about new suffix insertion when you have active_point (root, '\x0', 0): doesn't this mean that you have to iterate through all edges starting at the root to find the appropriate one? If yes then this operation is not constant since the number of edges starting at the root depends on the input, is this OK? – some Apr 28 '14 at 14:18

0 Answers0