What is a time complexity for checking a string of length n is substring or not?(a) O (log n!)(b) O (n!)(c) O (n^2)(d) O (n)My question is taken from Suffix Tree in chapter Trie of Data Structures & Algorithms II have been asked this question by my college professor while I was bunking the class.

What is a time complexity for checking a string of length n is substri

1.	What is a time complexity for checking a string of length n is substring or not?(a) O (log n!)(b) O (n!)(c) O (n^2)(d) O (n)My question is taken from Suffix Tree in chapter Trie of Data Structures & Algorithms II have been asked this question by my college professor while I was bunking the class.
Answer» Correct OPTION is (d) O (N) Explanation: Suffix tree is also known as PAT tree or position tree. It allows fast STRING operation. Total time taken for construction of suffix tree is linear to the length of the tree. 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).

Discussion

No Comment Found

Related InterviewSolutions

Trie is also known as _________(a) Digital Tree(b) Treap(c) Binomial Tree(d) 2-3 TreeI want to ask this question from Trie topic in chapter Trie of Data Structures & Algorithms IThis question was addressed to me in a job interview.
What traversal over trie gives the lexicographical sorting of the set of the strings?(a) postorder(b) preorders(c) inorder(d) level orderI need to ask this question from Trie in chapter Trie of Data Structures & Algorithms IThis question was posed to me in homework.
Which of the following is the efficient data structure for searching words in dictionaries?(a) BST(b) Linked List(c) Balancded BST(d) TrieMy question comes from Trie in chapter Trie of Data Structures & Algorithms IThis question was addressed to me in semester exam.
Which of the following special type of trie is used for fast searching of the full texts?(a) Ctrie(b) Hash tree(c) Suffix tree(d) T treeOrigin of the question is Trie topic in chapter Trie of Data Structures & Algorithms II got this question in a job interview.
Which of the following is not true?(a) Trie requires less storage space than hashing(b) Trie allows listing of all the words with same prefix(c) Tries are collision free(d) Trie is also known as prefix treeQuestion is taken from Trie topic in division Trie of Data Structures & Algorithms II had been asked this question in an online quiz.
A program to search a contact from phone directory can be implemented efficiently using ______(a) a BST(b) a trie(c) a balanced BST(d) a binary treeMy question is based upon Trie in division Trie of Data Structures & Algorithms II had been asked this question in class test.
What can be the maximum depth of the trie with n strings and m as the maximum sting the length?(a) log2n(b) log2m(c) n(d) mMy doubt is from Trie in division Trie of Data Structures & Algorithms IThis question was addressed to me at a job interview.
Which of the following is true about the trie?(a) root is letter a(b) path from root to the leat yields the string(c) children of nodes are randomly ordered(d) each node stores the associated keysThis intriguing question originated from Trie topic in section Trie of Data Structures & Algorithms II had been asked this question during an online exam.
Auto complete and spell checkers can be implemented efficiently using the trie.(a) True(b) FalseEnquiry is from Trie in portion Trie of Data Structures & Algorithms IThis question was posed to me during an interview for a job.
What is the other name for Suffix Tree?(a) Array(b) Stack(c) Priority Queue(d) PAT TreeAsked question is from Suffix Tree topic in division Trie of Data Structures & Algorithms IThis question was posed to me in my homework.

What is a time complexity for checking a string of length n is substring or not?(a) O (log n!)(b) O (n!)(c) O (n^2)(d) O (n)My question is taken from Suffix Tree in chapter Trie of Data Structures & Algorithms II have been asked this question by my college professor while I was bunking the class.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment