Talk:Suffix tree: Difference between revisions
→definition?
Line 28:
What is the missing part of this definition? --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 16:33, 23 May 2013 (UTC)
: On every node, each edge leading away from it must start with a unique letter. So the suffix tree of string "aa$" can't have two edges "a$" and "aa$" leading away from the root node. Instead it must have one edge "a" pointing to a second node, which in turn has two outgoing edges "a$" and "$". The reason for unique leading letters is that, otherwise when matching substrings, one can't decide which edge to follow at each node in O(1) time. --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 13:02, 24 May 2013 (UTC)
:: I'm still not seeing how to make this work in O(1) time (interpreting the big-O notation as representing worst case behavior). Let's say our string is an arbitrary length sequence of a single letter (followed by the terminating character). Now we have a single node and the number of edges we have to pick between is O(n) and we need something like an oracle (or luck or a complete scan) to tell us which of them we need to follow. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 19:39, 24 May 2013 (UTC)
| |||