Suffix tree of 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.
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:ooooloomoollooW#)|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