+1 vote
in Data Structures & Algorithms I by (110k points)
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.

1 Answer

+1 vote
by (408k points)
selected by
 
Best answer
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.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.

Categories

...