Suffix tree of Woolloomooloo

LA home
Computing
Algorithms
 glossary
 Binary Trees
  Search T'
  Tries
  PATRICIA
  Suffix Trees
 Tables
  Woolloomooloo

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
www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Thursday, 02-May-2024 17:19:31 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.