Brute-force Construction

• Like McCreight, but add succesive p-suffix entries

• S={a,b,c,$},? ={v,x,y}

S=xbyybx$

psuffix(S,1)=0b01b5$

(S,2)=b01b0$

(S,3)=01b0$

(S,4)= 1b0$

(S,5)=b0$

(S,6)=0$

Searching:

follow symbols from prev(p)

p=vbx$

prev(p)=0b0$

Time: O(|P|log(|S |+|? |)

Previous slide

Next slide

Back to first slide

View graphic version