KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
Input: string S = AAGATATGATAGGAT. Output: Maximal repeats such as GATA (as in positions 3 and 8), GAT (as in position 3, 8 and 13) and so on... A maximal repeat is a substring t occurs k>1 times in S, and if t is extended to left or right, it will occur less than k times. An internal node’s leaf descendants are suffixes, each of which has a left character. If the left characters of all leaf descendants are not all identical, it’s called a “left-diverse” node. Maximal repeats is left-diverse internal nodes. Overall idea: Build a suffix tree and then do a DFS (depth first search) on the tree For each leaf, label it with its left character For each internal node: If at least one child is labelled with *, then label it with * Else if its children’s labels are diverse, label with *. Else then all children have same label, copy it to current node Is the above idea is correct? How does the pseudo-code to be? Then I can try to write programming myself.
Tags (comma-separated)
Save Edits
Cancel