+1 vote
in Data Structures & Algorithms I by (88.2k points)
What is a time complexity for finding the longest substring that is common in string S1 and S2 (n1 and n2 are the string lengths of strings s1, s2 respectively)?

(a) O (log n!)

(b) Ɵ (n!)

(c) O (n^2+ n1)

(d) Ɵ (n1 + n2)

Question is taken from Suffix tree in chapter Trie of Data Structures & Algorithms I

I had been asked this question at a job interview.

1 Answer

+1 vote
by (672k points)
selected by
 
Best answer
The correct answer is (d) Ɵ (n1 + n2)

Easy explanation - Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the longest substring that is common in string S1 and S2 is Ɵ (n1 + n2).

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

...