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

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

a) O(nm)
b) O(n2)
c) O(mnlogn)
d) O(mlogn)

Answer: d
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.

Comments