Talk:Suffix tree: Difference between revisions
Content added Content deleted
(Created page with "==Different test case?== Can we use maybe "banana" from the WP page instead? "rosettacode" simply doesn't have enough interesting repetitions. --~~~~") |
(→definition?: new section) |
||
| Line 1: | Line 1: | ||
==Different test case?== |
==Different test case?== |
||
Can we use maybe "banana" from the WP page instead? "rosettacode" simply doesn't have enough interesting repetitions. --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 17:58, 17 May 2013 (UTC) |
Can we use maybe "banana" from the WP page instead? "rosettacode" simply doesn't have enough interesting repetitions. --[[User:Ledrug|Ledrug]] ([[User talk: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 <math>S</math> of length <math>n</math> is defined as a tree such that:<ref>{{harvtxt|Gusfield|1999}}, p.90.</ref> |
|||
:* the paths from the root to the leaves have a one-to-one relationship with the suffixes of <math>S</math>, |
|||
:* edges spell non-empty strings, |
|||
:* and all internal nodes (except perhaps the root) have at least two children. |
|||
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? --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 16:33, 23 May 2013 (UTC) |
|||
Revision as of 16:33, 23 May 2013
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 of length is defined as a tree such that:[1]
- the paths from the root to the leaves have a one-to-one relationship with the suffixes of ,
- edges spell non-empty strings,
- and all internal nodes (except perhaps the root) have at least two children.
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)
- ↑ Template:Harvtxt, p.90.