How can we search for an occurrence of P in T with a Suffix Array in O(mlogn + occ) time?
What's the name of the method used to build a suffix array in O(n) time?
The DC3 method requires sorting the blocks in R in O(n) time. Which algorithm can be used? What assumption is made?
In the DC3 method, what are the sizes of the blocks in R1 and R2?
Finding an occurrence of a pattern P takes O(mlogn) time. (O(logmn + occ)). What can this be improved to with LCP queries?