Question

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.

Answer 1

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.