Hi Gene, this help of yours is much appreciated. Thanks a lot.
On 3/15/12, Gene gene.ress...@gmail.com wrote:
In case you want to play with this, here is a little program
that computes suffix trees with a simple brute force algorithm
and prints their sizes. It looks like the actual growth is
In case you want to play with this, here is a little program
that computes suffix trees with a simple brute force algorithm
and prints their sizes. It looks like the actual growth is
O(m^2). So my quick analysis was too conservative:
m=1 chars=0
m=3 chars=3
m=6 chars=11
m=10 chars=29
m=15
{ reverse( $ a b a a b b a a a b b b ... a^n b^n ) | n = 0,1,2,... }
On Mar 13, 12:47 am, reynald reni reni.reyn...@gmail.com 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'
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
