I have specific question about suffix trees. I am reading the book Algorithms on strings_trees and sequence. I cannot understand details of Ukkonen's algorithm for constructing suffix trees. Why using the skip/count trick, any phase of Ukkonen's algorithm takes O(m) time (theorem 6.1.1)? In particular why over the entire phase, the total number of edge traversals during down-walks is bounded by by 3m?

  • 5
    $\begingroup$ I am not sure wether this question has the appropriate level for this site. It would have been perfect for the upcoming Computer Science Stack Exchange, though. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! $\endgroup$ – Raphael Feb 20 '12 at 21:50
  • 1
    $\begingroup$ @Raphael I committed to CS stack exchange. $\endgroup$ – ashim Feb 21 '12 at 0:25
  • 5
    $\begingroup$ See this answer on StackOverflow: stackoverflow.com/a/9513423/336563 $\endgroup$ – ziggurism Apr 12 '12 at 0:26
  • 2
    $\begingroup$ and cs.SE is open for business now :) $\endgroup$ – Suresh Venkat Apr 12 '12 at 3:59
  • 2
    $\begingroup$ It's been 11 hours since Joe's comment; the number of upvotes is now 573. $\endgroup$ – Jeffε Apr 12 '12 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.