2
$\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
    $\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 '12 at 6:22
  • $\begingroup$ I have a very rough idea of McCreight's suffix tree construction algorithm. $\endgroup$ – Wuschelbeutel Kartoffelhuhn Nov 27 '12 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 '12 at 8:22
8
$\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$
  • $\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$ – Wuschelbeutel Kartoffelhuhn Nov 27 '12 at 7:53
  • $\begingroup$ Yes it is ${n \choose 2}=n(n-1)/2=\Theta(n^2)$. $\endgroup$ – A.Schulz Nov 27 '12 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 '12 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$ – user1771809 Nov 29 '12 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$ – clyton dantis Mar 20 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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