Suffix tree of Woolloomooloo

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

Algorithms
 glossary
 Binary Trees
  Search T'
  23trees
  234trees
  Btrees
  Tries
  PATRICIA
  Suffix Trees

 Tables

W

     |(1:W)|leaf

Wo

suffixes Wo and o

     |(1:Wo)|leaf
     |
tree:|
     |
     |(2:o)|leaf

Woo

suffixes Woo, oo and o, well oo covers the last two cases on its own.

     |(1:Woo)|leaf
     |
tree:|
     |
     |(2:oo)|leaf

Wool

Wool, ool, ol and l;  oo+l splits to ool and ol.

     |(1:Wool)|leaf
     |
tree:|
     |     |(3:ol)|leaf
     |(2:o)|
     |     |(4:l)|leaf
     |
     |
     |(4:l)|leaf

Wooll

ll covers ll and also l.

     |(1:Wooll)|leaf
     |
tree:|
     |     |(3:oll)|leaf
     |(2:o)|
     |     |(4:ll)|leaf
     |
     |
     |(4:ll)|leaf

Woollo

ll+o splits to llo and lo.

     |(1:Woollo)|leaf
     |
tree:|
     |     |(3:ollo)|leaf
     |(2:o)|
     |     |(4:llo)|leaf
     |
     |
     |     |(5:lo)|leaf
     |(4:l)|
     |     |(6:o)|leaf

Woolloo

     |(1:Woolloo)|leaf
     |
tree:|
     |     |(3:olloo)|leaf
     |(2:o)|
     |     |(4:lloo)|leaf
     |
     |
     |     |(5:loo)|leaf
     |(4:l)|
     |     |(6:oo)|leaf

Woolloom

oo... splits to ool... and oom. Also m is new.

     |(1:Woolloom)|leaf
     |
tree:|
     |     |     |(4:lloom)|leaf
     |     |(3:o)|
     |     |     |(8:m)|leaf
     |     |
     |(2:o)|
     |     |(4:lloom)|leaf
     |     |
     |     |(8:m)|leaf
     |
     |
     |     |(5:loom)|leaf
     |(4:l)|
     |     |(6:oom)|leaf
     |
     |(8:m)|leaf

Woolloomo

     |(1:Woolloomo)|leaf
     |
tree:|
     |     |     |(4:lloomo)|leaf
     |     |(3:o)|
     |     |     |(8:mo)|leaf
     |     |
     |(2:o)|
     |     |(4:lloomo)|leaf
     |     |
     |     |(8:mo)|leaf
     |
     |
     |     |(5:loomo)|leaf
     |(4:l)|
     |     |(6:oomo)|leaf
     |
     |(8:mo)|leaf

Woolloomoo

No split -- already had oo....

     |(1:Woolloomoo)|leaf
     |
tree:|
     |     |     |(4:lloomoo)|leaf
     |     |(3:o)|
     |     |     |(8:moo)|leaf
     |     |
     |(2:o)|
     |     |(4:lloomoo)|leaf
     |     |
     |     |(8:moo)|leaf
     |
     |
     |     |(5:loomoo)|leaf
     |(4:l)|
     |     |(6:oomoo)|leaf
     |
     |(8:moo)|leaf

Woolloomool

No split -- already had ool....

     |(1:Woolloomool)|leaf
     |
tree:|
     |     |     |(4:lloomool)|leaf
     |     |(3:o)|
     |     |     |(8:mool)|leaf
     |     |
     |(2:o)|
     |     |(4:lloomool)|leaf
     |     |
     |     |(8:mool)|leaf
     |
     |
     |     |(5:loomool)|leaf
     |(4:l)|
     |     |(6:oomool)|leaf
     |
     |(8:mool)|leaf

Woolloomoolo

Split to ooll... and oolo etc.

     |(1:Woolloomoolo)|leaf
     |
tree:|
     |     |     |     |(5:loomoolo)|leaf
     |     |     |(4:l)|
     |     |     |     |(12:o)|leaf
     |     |(3:o)|
     |     |     |(8:moolo)|leaf
     |(2:o)|
     |     |     |(5:loomoolo)|leaf
     |     |(4:l)|
     |     |     |(12:o)|leaf
     |     |
     |     |
     |     |(8:moolo)|leaf
     |
     |     |(5:loomoolo)|leaf
     |(4:l)|
     |     |(6:oomoolo)|leaf
     |
     |(8:moolo)|leaf

Woolloomooloo

Extensions, no new splits.

     |(1:Woolloomooloo)|leaf
     |
tree:|
     |     |     |     |(5:loomooloo)|leaf
     |     |     |(4:l)|
     |     |     |     |(12:oo)|leaf
     |     |(3:o)|
     |     |     |(8:mooloo)|leaf
     |(2:o)|
     |     |     |(5:loomooloo)|leaf
     |     |(4:l)|
     |     |     |(12:oo)|leaf
     |     |
     |     |
     |     |(8:mooloo)|leaf
     |
     |     |(5:loomooloo)|leaf
     |(4:l)|
     |     |(6:oomooloo)|leaf
     |
     |(8:mooloo)|leaf

Woolloomooloo$

Add an end-of-string character, `$', split to oom... and oo$ etc..

     |(1:Woolloomooloo$)|leaf
tree:|
     |     |     |     |(5:loomooloo$)|leaf
     |     |     |(4:l)|
     |     |     |     |(12:oo$)|leaf
     |     |(3:o)|
     |     |     |(8:mooloo$)|leaf
     |     |     |
     |     |     |(14:$)|leaf
     |(2:o)|
     |     |     |(5:loomooloo$)|leaf
     |     |(4:l)|
     |     |     |(12:oo$)|leaf
     |     |
     |     |(8:mooloo$)|leaf
     |     |
     |     |(14:$)|leaf
     |
     |     |(5:loomooloo$)|leaf
     |(4:l)|
     |     |      |(8:mooloo$)|leaf
     |     |(6:oo)|
     |     |      |(14:$)|leaf
     |
     |(8:mooloo$)|leaf
     |
     |(14:$)|leaf

Longest repeated substring

``ool'' in red above (or loo) -- deepest split/string with at least two descendants.

Longest Palindrome

i.e. Input   Woolloomooloo$ooloomoollooW#, and the longest palindrome is ``loomool'', i.e. the deepest fork-node (7-characters) with both a ``...$...'' and a ``...#'' sub-tree -- in red below:

     |     |(2:oolloomooloo$ooloomoollooW#)|leaf
     |(1:W)|
     |     |(28:#)|leaf
tree:|
     |     |     |     |       |(8:mooloo$ooloomoollooW#)|leaf
     |     |     |     |(5:loo)|
     |     |     |     |       |(27:W#)|leaf
     |     |     |(4:l)|
     |     |     |     |       |(14:$ooloomoollooW#)|leaf
     |     |     |     |(12:oo)|
     |     |     |     |       |(20:moollooW#)|leaf
     |     |(3:o)|
     |     |     |        |(12:oo$ooloomoollooW#)|leaf
     |     |     |(8:mool)|
     |     |     |        |(24:looW#)|leaf
     |     |     |
     |     |     |(14:$ooloomoollooW#)|leaf
     |     |     |
     |     |     |(27:W#)|leaf
     |(2:o)|
     |     |     |       |(8:mooloo$ooloomoollooW#)|leaf
     |     |     |(5:loo)|
     |     |     |       |(27:W#)|leaf
     |     |(4:l)|
     |     |     |       |(14:$ooloomoollooW#)|leaf
     |     |     |(12:oo)|
     |     |     |       |(20:moollooW#)|leaf
     |     |
     |     |        |(12:oo$ooloomoollooW#)|leaf
     |     |(8:mool)|
     |     |        |(24:looW#)|leaf
     |     |
     |     |(14:$ooloomoollooW#)|leaf
     |     |
     |     |(27:W#)|leaf
     |
     |     |       |(8:mooloo$ooloomoollooW#)|leaf
     |     |(5:loo)|
     |     |       |(27:W#)|leaf
     |(4:l)|
     |     |      |        |(12:oo$ooloomoollooW#)|leaf
     |     |      |(8:mool)|
     |     |      |        |(24:looW#)|leaf
     |     |(6:oo)|
     |     |      |(14:$ooloomoollooW#)|leaf
     |     |      |
     |     |      |(27:W#)|leaf
     |
     |        |(12:oo$ooloomoollooW#)|leaf
     |(8:mool)|
     |        |(24:looW#)|leaf
     |
     |(14:$ooloomoollooW#)|leaf
     |
     |(28:#)|leaf

See the interactive [suffix tree (click)] demonstration.

-- LA 5/2002
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser
© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Tuesday, 16-Apr-2024 22:29:49 AEST.