### Suffix tree of Woolloomooloo

 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

```     |(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

```     |(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
window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

 © 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 Sunday, 21-Jan-2018 11:47:51 AEDT.