Talk:Suffix tree

Different test case?

Can we use maybe "banana" from the WP page instead? "rosettacode" simply doesn't have enough interesting repetitions. --Ledrug (talk) 17:58, 17 May 2013 (UTC)

definition?

The wikipedia definition for a suffix tree currently looks like this:

The suffix tree for the string $S$ of length $n$ is defined as a tree such that:

• the paths from the root to the leaves have a one-to-one relationship with the suffixes of $S$,
• edges spell non-empty strings,
• and all internal nodes (except perhaps the root) have at least two children.

Template:Harvtxt, p.90.

But this can be satisfied by a tree with only a root where each node is a unique suffix. Something is missing from this definition, and that something seems to have something to do with substrings which appear in multiple locations in the string.

What is the missing part of this definition? --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. --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. --Rdm (talk) 19:39, 24 May 2013 (UTC)