What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?

Category: QuestionsWhat is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?
Editor">Editor Staff asked 2 months ago

What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?
 
(a) O(S1)
 
(b) O(S2)
 
(c) O(S1+S2)
 
(d) O(1)
 
This interesting question is from Propositional and Directed Acyclic Word Graph topic in section Graph of Data Structures & Algorithms I
 
This question was posed to me during an online interview.

1 Answers
Editor">Editor Staff answered 2 months ago

Correct option is (a) O(S1)
 
Easiest explanation – For each check of a word of length  S1, we need to follow at most S1 edges.