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 chars=67
m=21 chars=137
m=28 chars=254
m=36 chars=436
m=45 chars=704
m=55 chars=1082
m=66 chars=1597
m=78 chars=2279
m=91 chars=3161
m=105 chars=4279
m=120 chars=5672
m=136 chars=7382
m=153 chars=9454
m=171 chars=11936
m=190 chars=14879
m=210 chars=18337
m=231 chars=22367
m=253 chars=27029
m=276 chars=32386
m=300 chars=38504
m=325 chars=45452
m=351 chars=53302
m=378 chars=62129
m=406 chars=72011
m=435 chars=83029
m=465 chars=95267
m=496 chars=108812
m=528 chars=123754
m=561 chars=140186
m=595 chars=158204
m=630 chars=177907
m=666 chars=199397
m=703 chars=222779
m=741 chars=248161
m=780 chars=275654
m=820 chars=305372
m=861 chars=337432
m=903 chars=371954
m=946 chars=409061
m=990 chars=448879
m=1035 chars=491537
public class SuffixTreeProblem {
// We store strings implicitly. If there is an "a" child,
// there is an "a" edge out of the node. If dollar is
// true then this node marks the end of a suffix.
static class Node {
Node a = null, b = null;
boolean dollar = false;
}
// Produce a string that requires a big suffix tree.
byte [] genString(int n) {
byte [] s = new byte [1 + n + n * (n + 1) / 2];
int i = 0;
for (int in = n; in > 0; in--) {
s[i++] = 'b';
for (int j = 0; j < in; j++) {
s[i++] = 'a';
}
}
s[i] = '$';
return s;
}
// Brute force: Build the tree counting characters used.
int suffixTreeChars(byte [] s) {
Node tree = new Node();
int n = 0;
for (int iStart = s.length - 1; iStart >= 0; --iStart) {
Node p = tree;
for (int i = iStart; ; ++i) {
if (s[i] == '$') {
p.dollar = true;
break;
}
else if (s[i] == 'a') {
if (p.a == null) {
p.a = new Node();
++n;
}
p = p.a;
}
else {
if (p.b == null) {
p.b = new Node();
++n;
}
p = p.b;
}
}
}
return n;
}
void test() {
for (int n = 0; n < 50; ++n) {
byte [] s = genString(n);
int m = s.length;
System.out.println("m=" + m + " chars=" +
suffixTreeChars(s));
}
}
public static void main(String [] argv) {
new SuffixTreeProblem().test();
}
}
On Mar 14, 1:06 am, Gene <[email protected]> wrote:
> 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.
