adplus-dvertising
frame-decoration

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)

Answer: (a).O(S1)

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. 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?

Similar Questions

Discover Related MCQs

Q. In which of the following case does a Propositional Directed Acyclic Graph is used for?

Q. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.

Q. In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.

Q. Given Adjacency matrices determine which of them are PseudoGraphs?

i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

Q. All undirected Multigraphs contain eulerian cycles.

Q. Determine the number of vertices for the given Graph or Multigraph?
G is a 4-regular Graph having 12 edges.

Q. Which of the following statement is true.

Q. Given Adjacency matrices determine which of them are PseudoGraphs?
i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

Q. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?

Q. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?

Q. What would be the Incidence Matrix of the given HyperGraph?
V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}

Q. What is the degree sequence of the given HyperGraph, in non-increasing order.
V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}

Q. MultiGraphs having self-loops are called PseudoGraphs?

Q. Binary Decision Diagram is a type of __________

Q. In which of the following case does a Binary Decision Diagram is used for?

Q. In a Binary Decision Diagram, how many types of terminal exists?

Q. In a Binary Decision Diagrams 0 values by a _________ line and the 1 values are represented by a _________ line.

Q. How many nodes are required to create a Binary Decision Tree having 4 variables?

Q. Two or more And Inverter Graphs can represent same function.

Q. Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.