What can you do with a suffix array?Can't stream text -- no suffix linksCan do pattern lookup in O(|P|log|S|) time find(P): i = 0 lo = 0, hi = length(A) for 0<=i<length(P): Binary search for x,y where P[i]=S[A[j]+i] for lo<=x<=j<y<=hi lo = x, hi = y return {A[lo],A[lo+1],...,A[hi-1]} Can do pattern lookup in O(|P|) time (different method than above)Can build `in place' in O(|S| log|S|) timeAlphabe