Suffix tree: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl 6}}: stabilize output, work-around for JVM bug) |
m (added whitespace to the task's preamble.) |
||
Line 10: | Line 10: | ||
* No two edges starting out of a node can have string labels beginning with the same character. |
* No two edges starting out of a node can have string labels beginning with the same character. |
||
* The string obtained by concatenating all the string labels found on the path from the root to leaf i spells out suffix S[i..n], for i from 1 to n. |
* The string obtained by concatenating all the string labels found on the path from the root to leaf i spells out suffix S[i..n], for i from 1 to n. |
||
Such a tree does not exist for all strings. To ensure existence, a character that is not found in S must be appended at its end. The character '$' is traditionally used for this purpose. |
Such a tree does not exist for all strings. To ensure existence, a character that is not found in S must be appended at its end. The character '$' is traditionally used for this purpose. |