3
$\begingroup$

Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.

$\endgroup$
3
  • 3
    $\begingroup$ Have you read some articles/papers/tutorials explaining how suffix trees can be constructed in linear time with linear space complexity? $\endgroup$
    – Paresh
    Nov 27, 2012 at 6:22
  • $\begingroup$ I have a very rough idea of McCreight's suffix tree construction algorithm. $\endgroup$ Nov 27, 2012 at 6:25
  • 4
    $\begingroup$ They may be $\approx n^2$ many substrings, but suffix strings only store suffices, which there are only linearly many of. $\endgroup$
    – Raphael
    Nov 27, 2012 at 8:22

1 Answer 1

9
$\begingroup$

For a text of length $n$ we have up to $1+{ n+1 \choose 2}$ different substrings, however there are only $n+1$ suffixes (for every suffix you can pick the position where it starts).

I assume you consider the compressed suffix tree (edge labels are words). This is a tree with $n+1$ leaves and every internal node has at least two children. Thus we have less interior nodes than leaves an therefore the tree has size $O(n)$.

Notice that in the uncompressed version (edge labels a characters) with a large alphabet, you can have super-linear suffix trees. For example, consider the text abcdefghijk....

$\endgroup$
6
  • $\begingroup$ thanks for your answer. is n choose 2 (i.e., the max number of unique substrings in a string) order of n^2? $\endgroup$ Nov 27, 2012 at 7:53
  • $\begingroup$ Yes it is ${n \choose 2}=n(n-1)/2=\Theta(n^2)$. $\endgroup$
    – A.Schulz
    Nov 27, 2012 at 7:56
  • $\begingroup$ @A.Schulz I think there is a small mistake in the number of unique substrings. It should be $1 + {{n+1} \choose 2}$. ${n \choose 2}$ does not take into account single alphabet substrings. $\endgroup$
    – Paresh
    Nov 27, 2012 at 8:01
  • $\begingroup$ @Paresh How are you getting $1+\binom{n+1}{2}$? On wiki it is given as $\binom{n+1}{2}$. $\endgroup$ Nov 29, 2012 at 10:50
  • $\begingroup$ How is it guaranteed that the internal nodes will have at least 2 children? As per my understanding, number of children depends on the number of suffixes that start from that node. How did you count the children for the internal nodes? $\endgroup$
    – Clyt
    Mar 20, 2019 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.