Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

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

1 Answer

up vote 3 down vote accepted

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....

share|improve this answer
thanks for your answer. is n choose 2 (i.e., the max number of unique substrings in a string) order of n^2? – Wuschelbeutel Kartoffelhuhn Nov 27 '12 at 7:53
Yes it is ${n \choose 2}=n(n-1)/2=\Theta(n^2)$. – A.Schulz Nov 27 '12 at 7:56
@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. – Paresh Nov 27 '12 at 8:01
@Paresh: Thanks for the pointer – A.Schulz Nov 27 '12 at 8:07
@Paresh How are you getting $1+\binom{n+1}{2}$? On wiki it is given as $\binom{n+1}{2}$. – user1771809 Nov 29 '12 at 10:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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