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.
$\begingroup$
$\endgroup$
3
asked Nov 27, 2012 at 5:43
-
3$\begingroup$ Have you read some articles/papers/tutorials explaining how suffix trees can be constructed in linear time with linear space complexity? $\endgroup$– PareshNov 27, 2012 at 6:22
-
$\begingroup$ I have a very rough idea of McCreight's suffix tree construction algorithm. $\endgroup$– Wuschelbeutel KartoffelhuhnNov 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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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....
-
$\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.SchulzNov 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$– PareshNov 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$– ClytMar 20, 2019 at 4:13