2807412
| Question | Answer |
| How can we search for an occurrence of P in T with a Suffix Array in O(mlogn + occ) time? | Using binary search |
| What's the name of the method used to build a suffix array in O(n) time? | DC3 Method |
| The DC3 method requires sorting the blocks in R in O(n) time. Which algorithm can be used? What assumption is made? | Radix Sort The bit representation of each symbol uses O(logn) bits. |
| In the DC3 method, what are the sizes of the blocks in R1 and R2? | 3 |
| Finding an occurrence of a pattern P takes O(mlogn) time. (O(logmn + occ)). What can this be improved to with LCP queries? | O(m + logn + occ) |
Want to create your own Flashcards for free with GoConqr? Learn more.