Talk:Suffix tree: Difference between revisions
Content added Content deleted
m (try to address the missing reference message ... looks plausible in preview, let's see if it really works...) |
|||
| Line 11: | Line 11: | ||
:* and all internal nodes (except perhaps the root) have at least two children. |
:* and all internal nodes (except perhaps the root) have at least two children. |
||
:<references> |
|||
*{{citation |
|||
| last1 = Barsky | first1 = Marina |
| last1 = Barsky | first1 = Marina |
||
| last2 = Stege | first2 = Ulrike |
| last2 = Stege | first2 = Ulrike |
||
| Line 21: | Line 22: | ||
| publisher = ACM |
| publisher = ACM |
||
| title = CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management |
| title = CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management |
||
| year = 2008}}. |
| year = 2008}}.</references> |
||
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. |
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. |
||
Revision as of 16:37, 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)