## [Solved] Which of the following is/are advantages suffix array one suffix tree?

Which of the following is/are advantages suffix array one suffix tree? I. Lesser space requirementII. Improved cache localityIII. Easy construction in linear time a) Only Ib) All I, II, and IIIc) Only I and IIId) Only II and III Answer: bExplanation: Advantages of the suffix array over suffix tree are : (i) Lesser space requirement …

## [Solved] Suffix array can be created in O(nlogn) time

Suffix array can be created in O(nlogn) time. a) Trueb) False Answer: aExplanation: Suffix array can be constructed in O(n2logn) time using sorting algorithms but it is possible to build the suffix array in O(nlogn) time using prefix doubling.

## [Solved] What is the time required to locate the occurrences of a pattern P of length m in a string of length n using a suffix array?

What is the time required to locate the occurrences of a pattern P of length m in a string of length n using a suffix array? a) O(nm)b) O(n2)c) O(mnlogn)d) O(mlogn) Answer: dExplanation: Suffix arrays are used to find the occurrences of a pattern in a string. Pattern of length m will require m characters …

## [Solved] LCP array and ______ is used to construct suffix tree.

LCP array and ______ is used to construct suffix tree. a) Hash treeb) Hash triec) Suffix arrayd) Balanced tree Answer: cExplanation: A suffix tree can be created using an LCP array and a suffix array. If we are given a string of length (n + 1) and its suffix array and LCP array, we can …

## [Solved] What will be the suffix array of the string “engineering”?

What will be the suffix array of the string “engineering”? a) 2 3 8 4 9 1 7 5 0 6 10b) 5 0 6 1 4 9 1 7 0 2 3 8c) 5 0 6 10 2 4 9 1 7 3 8d) 5 0 6 10 2 3 8 4 9 1 …

## [Solved] If comparison based sorting algorithm is used construct the suffix array, then what will be time required to construct the suffix array?

If comparison based sorting algorithm is used construct the suffix array, then what will be time required to construct the suffix array? a) O(nlogn)b) O(n2)c) O(n2logn)d) O(n2) + O(long) Answer: cExplanation: On average comparison based sorting algorithms require O(nlogn) comparisons. But comparing a suffix takes O(n). So, overall time to construct the suffix array will …

## [Solved] Suffix array is space efficient and faster than the suffix tree

Suffix array is space efficient and faster than the suffix tree. a) Trueb) False Answer: bExplanation: Suffix arrays are more space-efficient than the suffix trees as they just store the original string and an array of integers. But working with the suffix tree is faster than that of the suffix array.

## [Solved] Suffix array can be created by performing __________ traversal of a suffix tree.

Suffix array can be created by performing __________ traversal of a suffix tree. a) breadth-firstb) level orderc) depth-firstd) either breadth-first or level order Answer: cExplanation: A suffix tree is a trie, which contains all the suffixes of the given string as their keys and positions in the string as their values. So, we can construct …

## [Solved] Suffix array of the string “statistics” is _____ (MCQ)

Suffix array of the string “statistics” is ______ a) 2 8 7 4 9 0 5 1 6 3b) 2 7 4 9 8 0 5 1 6 3c) 2 4 9 0 5 7 8 1 6 3d) 2 8 7 0 5 1 6 9 4 3 Answer: aExplanation: The suffix array of …

## [Solved] Which of the following is false? (MCQ)

Which of the following is false? a) Suffix array is always sortedb) Suffix array is used in string matching problemsc) Suffix array is always unsortedd) Suffix array contains all the suffixes of the given string Answer: cExplanation: The suffix array is always sorted as it contains all the suffixes of a string in sorted order. …