[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 …

Read more

[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 …

Read more

[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 …

Read more

[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 …

Read more