FIT3155: Week 4 Tutorial (Based on Week 3 topic)
Objectives: The tutorials, in general, give practice in problem solving, in analysis of algorithms and data-structures, and in mathematics and logic useful in the above. Attend and revise the lecture before attempting these questions.
Some uses of suffix trees
1. Reason how an (explicit) suffix tree of a string S could be used to answer the following problems:
Copyright By PowCoder代写 加微信 powcoder
Given a string t, find if t is a substring of S.
Givenastringt,findiftisasuffixofS.
Find the number of times a string t occurs in S as a substring. Find the smallest substrings of S occurring exactly k.
Find the longest repeated substring within S.
Find the lexicographically smallest suffix of S.
Find the suffix array of string S.
Warming up to suffix tree construction
2. Construct the explicit suffix trees and their corresponding implicit suf- fix trees for the following strings drawing both the edge labels and their efficient (space-saving) representations
abcdefg aaaaaaa abcabc
1 Tute sheet extended by
Ukkonen algorithm rules and insights
3. Build the implicit suffix tree for the string xabdxacxabe using the na ̈ıve O(n3) method without any tricks, recording the rule used at each phase and extension.
4. For each rule that was seen in phase i and extension j, reason what rule comes in the next phase i + 1 and the next extension j + 1. This should yield 6 inferences:
Rule1 in (j…i) =⇒ which Rule in (j…i+1) in the next phase? Rule2 in (j…i) =⇒ which Rule in (j…i+1) in the next phase? Rule3 in (j…i) =⇒ which Rule in (j…i+1) in the next phase? Rule1 in (j…i) =⇒ which Rule in (j+1…i) in the next extension? Rule2 in (j…i) =⇒ which Rule in (j+1…i) in the next extension? Rule3 in (j…i) =⇒ which Rule in (j+1…i) in the next extension?
5. Given the inferences above, how many Rule 2’s would need to be per- formed for a string of size n?
6. In what order does each rule occur in any given phase?
7. How can we exploit this ordering to save work on the rule 1’s and 3’s?
Traversing quickly
8. Revise skip-counting trick.
9. Reconstruct the implicit suffix tree for the string xabdxacxabe with all of the optimisations discussed so far in place, tracking the state of the main variables you would need, going between successive phases.
10. Reason the linear runtime of Ukkonen’s algorithm.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com