Let's try
{ reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } .
Note that m = n(n+1)/2 + n = O(n^2)
Think about adding suffixes to the tree from shortest to longest.
So suppose you are now adding something of the form
reverse( $ X a^L Y )
where L is the length of the longest run of a's and X and Y are what
comes before and after. Well we know the length of Y is at most L
and the length of X must be L(L-1)/2+(L-1) = L(L+1)/2 - 1 . What's
already in the tree will match no more than 2L characters before a new
branch occurs. The new branch will therefore have at least
L(L+1)/2 - 1 - 2L characters. This is O(L^2).
You should do the math more rigorously, but roughly you will be
getting for the total of all branches added,
sum_{L=0,1,..n} O(L^2) = O(n^3) = O(m ^ 1.5)
with one character per branch. This is super-linear.
On Mar 13, 12:47 am, reynald reni <[email protected]> wrote:
> Construct an infinite family of strings over a fixed alphabet, where
> the total length of the edge-labels on their suffix tree grows faster
> than O(m), where 'm' is the length of the string. [That is, show that
> linear time suffix tree algorithm would be impossible if edge-labels
> were written explicitly on the edges.]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
