Advanced Data Structures --- CMU Fall 2005 --- Sleator (original) (raw)

For a string S, suppose you are given the suffix array SA of S, and the longest common prefix array (LCP) of S, and a range-min query data structure for the LCP. Given these three data structures (and S), you want to efficiently answer queries of the form: Given a pattern P find the number of occurrences of P in S.

Part A: Give an algorithm that runs in time O(|P| log |S|).

Part B: Give an algorithm that runs in time O(|P| + log |S|).

Hint: You can use the LCP array along with the range-min structure to find the longest common prefix of any two suffixes in O(1) time.