Suffix Arrays

Description

Suffix Arrays
msladey
Flashcards by msladey, updated more than 1 year ago
msladey
Created by msladey over 9 years ago
8
0

Resource summary

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)
Show full summary Hide full summary

Similar

Mathematical Preliminaries
msladey
Hamming Distance
msladey
Suffix Trees
msladey
Range Minimum Query
msladey
Data Structures & Algorithms
Reuben Caruana
Computer science unit 2
Somto Ibeme
Algorithms ♡
lauren ♥
Computational Thinking ♡
lauren ♥
Searching and Sorting Algorithms
Josh Calvert
Systems Software Revision
cocacolai
Grafy I.
Michal Roch