Suffix Links – Example

BBBBBABABBBAABBBBB$

Insert suf14=BBBBB

head13=ABBB

u=A,v=B,w=BB

head14=BBBBB=vwz,z=BB

a

b

Node c

b

b

Node d

b

a..$

b..$

a..$

b

a..$

bb

a..$

bb$

head13

a..$

$

b

Step A: Node c is suffix link of uv

Step B - rescan: Node d is extended locus of vw

Step C – Scan: Extend from d to add node for z=BB

From head14, we can move on to head15….

How do we get to contracted locus for uv quickly?

from previous iteration’s Node d?

head14

Previous slide

Next slide

Back to first slide

View graphic version