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?

  1. Home
  2. Back

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?

1.O(S1)

2.O(S2)

3.O(S1+S2)

4.O(1)

Posted Date:-2022-05-13 10:07:03

More MCQS Questions and answers

  1. How many edges are there in a complete graph of order 9?
  2. A binary cycle space forms a ______ over the two element field.
  3. A bridge can not be a part of _______
  4. A cycle on n vertices is isomorphic to its complement. What is the value of n?
  5. A graph G has the degree of each vertex is ≥ 3 say, deg(V) ≥ 3 ∀ V ∈ G such that 3|V| ≤ 2|E| and 3|R| ≤ 2|E|, then the graph is said to be ________ (R denotes region in the graph)
  6. A graph which consists of disjoint union of trees is called ______
  7. A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).
  8. A linear graph consists of vertices arranged in a line.
  9. A polytree is called _______________
  10. A trail in a graph can be described as ______________
  11. A ______ in a graph G is a circuit which consists of every vertex (except first/last vertex) of G exactly once.
  12. A _______ is a graph with no homomorphism to any proper subgraph.
  13. Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______
  14. Determine the edge count of a path complement graph with 14 vertices.
  15. Every Isomorphic graph must have ________ representation.
  16. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______
  17. How many cycles are there in a wheel graph of order 5?
  18. How many perfect matchings are there in a complete graph of 10 vertices?
  19. If G is a simple graph with n-vertices and n>=3, the condition for G has a Hamiltonian circuit is __________
  20. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
  21. If two cycle graphs Gm and Gn are joined together with a vertex, the number of spanning trees in the new graph is ______
  22. In a directed weighted graph, if the weight of every edge is decreased by 10 units, does any change occur to the shortest path in the modified graph?
  23. In which of the following case does a Propositional Directed Acyclic Graph is used for?
  24. In which of the following does a Directed Acyclic Word Graph finds its application in?
  25. Let a graph can be denoted as ncfkedn a kind of ____________
  26. Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
  27. Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____
  28. Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?
  29. The maximum number of edges in a 8-node undirected graph without self loops is ____________
  30. The minimum number of edges in a connected cyclic graph on n vertices is _____________
  31. The sum of an n-node graph and its complement graph produces a graph called _______
  32. The topological sorting of any DAG can be done in ________ time.
  33. The tree elements are called __________
  34. The _______ of a graph G consists of all vertices and edges of G.
  35. Topological sorting of a graph represents _______ of a graph.
  36. Two labeled trees are isomorphic if ____________
  37. What is a bipartite graph?
  38. What is a separable graph?
  39. What is a star tree?
  40. What is the grade of a planar graph consisting of 8 vertices and 15 edges?
  41. What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?
  42. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
  43. 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?
  44. Which algorithm efficiently calculates the single source shortest paths in a Directed Acyclic Graph?
  45. Which of the given statement is true?
Search
R4R Team
R4Rin Top Tutorials are Core Java,Hibernate ,Spring,Sturts.The content on R4R.in website is done by expert team not only with the help of books but along with the strong professional knowledge in all context like coding,designing, marketing,etc!