Question

What is the time required to locate the occurrences of a pattern P of length m in a string of length n using suffix array?

(a) O(nm)

(b) O(n^2)

(c) O(mnlogn)

(d) O(mlogn)

My question comes from Arrays Types topic in portion Arrays Types of Data Structures & Algorithms I

The question was posed to me in an interview for internship.

Answer 1

Right option is (d) O(mlogn)

Explanation: Suffix arrays are used to find the occurrences of a pattern in a string. Pattern of length m will require m characters to compare, so using suffix array we can find occurrences of a pattern in the string of length n in O(mlogn) time.