<p>I have specific question about suffix trees. I am reading the book  <a href="http://books.google.com/books/about/Algorithms_on_strings_trees_and_sequence.html?id=STGlsyqtjYMC" rel="nofollow">Algorithms on strings_trees and sequence</a>.
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? </p>

CC BY-SA 3.0
2012-04-12T00:26:58.983Z
See this answer on StackOverflow: http://stackoverflow.com/a/9513423/336563
ziggurism
CC BY-SA 3.0
2012-04-12T03:59:18.800Z
and cs.SE is open for business now :)
Suresh Venkat
CC BY-SA 3.0
2012-04-12T07:18:46.603Z
wow and the answer over there (stackoverflow) has about 330 upvotes
Joe
CC BY-SA 3.0
2012-04-12T19:23:11.680Z
It's been 11 hours since Joe's comment; the number of upvotes is now 573.
Jeffε
CC BY-SA 3.0
2012-04-13T10:59:14.100Z
Talk about rep-cap.
Raphael
CC BY-SA 3.0
2012-02-20T21:50:45.553Z
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](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2), though. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off!
Raphael
CC BY-SA 3.0
2012-02-21T00:25:03.143Z
@Raphael I committed to CS stack exchange.
ashim
<ds.algorithms><graph-theory><graph-algorithms><string-matching>
suffix tree: about Ukkonen's algorithm
ashim
# suffix tree: about Ukkonen's algorithm

(Asked by: username_0 on 2012-02-20)

I have specific question about suffix trees. I am reading the book [Algorithms on strings\_trees and sequence](http://books.google.com/books/about/Algorithms_on_strings_trees_and_sequence.html?id=STGlsyqtjYMC).
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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, string-matching
> **Comments:**
> **username_5**: 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](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2), though. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off!  
> **username_0**: @Raphael I committed to CS stack exchange.  
> **username_1**: See this answer on StackOverflow: http://stackoverflow.com/a/9513423/336563  
> **username_2**: and cs.SE is open for business now :)  
> **username_3**: wow and the answer over there (stackoverflow) has about 330 upvotes  
> **username_4**: It's been 11 hours since Joe's comment; the number of upvotes is now 573.  
> **username_5**: Talk about rep-cap.  

---

## 0 answers

